46262023-03-30 12:55:30gortomiLegkisebb nem oszthatócpp17Wrong answer 10/1001.564s42128 KiB
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > g;
int tim = 0;
vector<int> l, r;
void dfs(int n, int p)
{
    l[n] = tim++;
    for(auto x : g[n]) if(x != p) dfs(x, n);
    r[n] = tim++;
}
struct val
{
    int l, r, ind;
};
bool comp(val a, val b)
{
    return a.l / 350 < b.l / 350 || (a.l / 350 == b.l / 350 && a.r < b.r);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> prim;
    vector<bool> ip(1e6 + 1, 1);
    vector<int> pl(1e6 + 1);
    g.resize(n + 1);
    l.resize(n + 1);
    r.resize(n + 1);
    for(int i = 2; i <= 1e6; i++)
    {
        if(ip[i])
        {
            pl[i] = prim.size();
            prim.push_back(i);
            for(int j = 2 * i; j <= 1e6; j += i)
            {
                ip[j] = 0;
            }
        }
    }
    vector<int> v(n + 1, 1e6 + 1);
    for(int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        if(ip[x]) v[i] = pl[x];
    }
    for(int i = 0; i < n - 1; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1, 0);
    vector<int> path(2 * n);
    for(int i = 1; i <= n; i++)
    {
        path[l[i]] = i;
        path[r[i]] = i;
    }
    int q;
    cin >> q;
    vector<val> que(q + 1);
    que[0] = {0, -1, 0};
    vector<int> ans(q);
    for(int i = 1; i <= q; i++)
    {
        int x, y;
        cin >> x >> y;
        que[i].l = r[x];
        que[i].r = l[y];
        if(que[i].l > que[i].r)
        {
            que[i].l = r[y];
            que[i].r = l[x];
        }
        que[i].ind = i - 1;
    }
    sort(que.begin(), que.end(), comp);
    const int b = 350;
    vector<int> sq(b);
    vector<int> db(n + 1);
    vector<bool> act(n + 1);
    for(int i = 1; i <= q; i++)
    {
        for(int j = que[i - 1].l - 1; j >= que[i].l; j--)
        {
            int y = path[j];
            int x = v[y];
            if(x > n) continue;
            if(!act[y])
            {
                act[y] = 1;
                db[x]++;
                if(db[x] == 1) sq[x / b]++;
            }
            else
            {
                act[y] = 0;
                db[x]--;
                if(db[x] == 0) sq[x / b]--;
            }
        }
        for(int j = que[i - 1].r + 1; j <= que[i].r; j++)
        {
            int y = path[j];
            int x = v[y];
            if(x > n) continue;
            if(!act[y])
            {
                act[y] = 1;
                db[x]++;
                if(db[x] == 1) sq[x / b]++;
            }
            else
            {
                act[y] = 0;
                db[x]--;
                if(db[x] == 0) sq[x / b]--;
            }
        }
        for(int j = que[i - 1].l; j <= que[i].l - 1; j++)
        {
            int y = path[j];
            int x = v[y];
            if(x > n) continue;
            if(!act[y])
            {
                act[y] = 1;
                db[x]++;
                if(db[x] == 1) sq[x / b]++;
            }
            else
            {
                act[y] = 0;
                db[x]--;
                if(db[x] == 0) sq[x / b]--;
            }
        }

        for(int j = que[i - 1].r; j >= que[i].r + 1; j--)
        {
            int y = path[j];
            int x = v[y];
            if(x > n) continue;
            if(!act[y])
            {
                act[y] = 1;
                db[x]++;
                if(db[x] == 1) sq[x / b]++;
            }
            else
            {
                act[y] = 0;
                db[x]--;
                if(db[x] == 0) sq[x / b]--;
            }
        }
        for(int j = 0; j < b; j++)
        {
            if(sq[j] < b)
            {
                for(int k = 0; k < b; k++)
                {
                    if(db[j * b + k] == 0)
                    {
                        ans[que[i].ind] = j * b + k;
                        break;
                    }
                }
                break;
            }
        }
    }
    for(auto x : ans) cout << prim[x] << "\n";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted17ms11076 KiB
subtask20/5
2Wrong answer17ms11292 KiB
3Wrong answer17ms11484 KiB
4Wrong answer17ms11716 KiB
5Accepted17ms11924 KiB
6Accepted18ms12268 KiB
7Accepted18ms12612 KiB
8Accepted18ms12684 KiB
9Accepted18ms12708 KiB
10Wrong answer19ms12796 KiB
11Wrong answer19ms12804 KiB
subtask30/5
12Accepted17ms12780 KiB
13Wrong answer17ms12868 KiB
14Wrong answer17ms13132 KiB
15Accepted17ms13216 KiB
16Accepted18ms13376 KiB
17Accepted18ms13596 KiB
18Accepted18ms13612 KiB
19Accepted18ms13400 KiB
20Wrong answer19ms13400 KiB
21Wrong answer19ms13588 KiB
subtask40/10
22Wrong answer35ms15200 KiB
23Wrong answer136ms19248 KiB
24Accepted248ms27652 KiB
25Wrong answer402ms34288 KiB
26Wrong answer569ms38584 KiB
27Wrong answer537ms38028 KiB
subtask50/10
28Wrong answer50ms15084 KiB
29Wrong answer181ms18200 KiB
30Wrong answer620ms25176 KiB
31Wrong answer1.223s30252 KiB
32Wrong answer1.536s32128 KiB
33Wrong answer1.564s32276 KiB
subtask610/10
34Accepted18ms14096 KiB
35Accepted32ms16052 KiB
36Accepted87ms20252 KiB
37Accepted193ms28484 KiB
38Accepted289ms36868 KiB
39Accepted358ms37376 KiB
40Accepted356ms40612 KiB
41Accepted372ms37500 KiB
subtask70/15
42Accepted18ms14196 KiB
43Accepted35ms15532 KiB
44Accepted104ms19388 KiB
45Accepted264ms25584 KiB
46Accepted485ms30964 KiB
47Accepted560ms32688 KiB
48Accepted561ms32680 KiB
49Accepted552ms32672 KiB
50Wrong answer620ms32700 KiB
51Wrong answer153ms36540 KiB
52Wrong answer156ms29176 KiB
53Wrong answer180ms35344 KiB
54Wrong answer150ms36628 KiB
55Wrong answer156ms29424 KiB
56Accepted1.511s29424 KiB
subtask80/20
57Wrong answer37ms16044 KiB
58Accepted87ms20712 KiB
59Wrong answer165ms24780 KiB
60Wrong answer488ms30504 KiB
61Accepted435ms39384 KiB
62Accepted361ms41664 KiB
63Wrong answer568ms38052 KiB
64Wrong answer556ms38880 KiB
65Wrong answer174ms42016 KiB
66Wrong answer165ms42128 KiB
subtask90/25
67Wrong answer43ms15752 KiB
68Accepted92ms18900 KiB
69Wrong answer206ms22252 KiB
70Wrong answer644ms26056 KiB
71Accepted537ms32540 KiB
72Accepted558ms32692 KiB
73Wrong answer1.182s32668 KiB
74Wrong answer837ms32676 KiB
75Wrong answer671ms32668 KiB
76Wrong answer838ms32760 KiB
77Wrong answer893ms32676 KiB
78Wrong answer742ms32700 KiB
79Wrong answer912ms32676 KiB
80Accepted374ms36392 KiB
81Accepted405ms36428 KiB
82Wrong answer179ms41740 KiB
83Wrong answer976ms37852 KiB