4682 2023. 03. 31 08:47:00 gortomi Legkisebb nem osztható cpp17 Elfogadva 100/100 1.585s 75600 KiB 
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > g, par;
int tim = 0;
vector<int> l, r, d;
void dfs(int n, int p)
{
    par[n][0] = p;
    d[n] = d[p] + 1;
    l[n] = tim++;
    for(int i = 1; i <= 19; i++)
    {
        par[n][i] = par[par[n][i - 1]][i - 1];
    }
    for(auto x : g[n]) if(x != p) dfs(x, n);
    r[n] = tim++;
}
struct val
{
    int l, r, ind, lca;
};
bool comp(val a, val b)
{
    return a.l / 350 < b.l / 350 || (a.l / 350 == b.l / 350 && a.r < b.r);
}
int calc(int a, int b)
{
    if(d[a] < d[b]) swap(a, b);
    int v = d[a] - d[b];
    for(int i = 0; i <= 19; i++)
    {
        if((v >> i) & 1) a = par[a][i];
    }
    for(int i = 19; i >= 0; i--)
    {
        if(par[a][i] != par[b][i])
        {
            a = par[a][i];
            b = par[b][i];
        }
    }
    return par[a][0];
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> prim;
    vector<bool> ip(2 * 1e6 + 1, 1);
    vector<int> pl(2 * 1e6 + 1);
    g.resize(n + 1);
    d.resize(n + 1);
    l.resize(n + 1);
    r.resize(n + 1);
    par.resize(n + 1, vector<int>(20));
    for(int i = 2; i <= 2 * 1e6; i++)
    {
        if(ip[i])
        {
            pl[i] = prim.size();
            prim.push_back(i);
            for(int j = 2 * i; j <= 2 * 1e6; j += i)
            {
                ip[j] = 0;
            }
        }
    }
    vector<int> v(n + 1, 2 * 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, 1);
    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, 0};
    vector<int> ans(q);
    for(int i = 1; i <= q; i++)
    {
        int x, y;
        cin >> x >> y;
        if(l[x] < l[y] && r[x] < r[y])
        {
            que[i].l = r[x];
            que[i].r = l[y];
            que[i].lca = calc(x, y);
        }
        else if(l[x] > l[y] && r[x] > r[y])
        {
            que[i].l = r[y];
            que[i].r = l[x];
            que[i].lca = calc(x, y);
        }
        else
        {
            que[i].l = l[x];
            que[i].r = l[y];
            if(que[i].l > que[i].r) swap(que[i].l, que[i].r);
            que[i].lca = 0;
        }
        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]--;
            }
        }
        int x = v[que[i].lca];
        if(x <= n)
        {
            db[x]++;
            if(db[x] == 1) 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;
            }
        }
        if(x <= n)
        {
            db[x]--;
            if(db[x] == 0) sq[x / b]--;
        }
    }
    for(auto x : ans) cout << prim[x] << "\n";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 35ms 20048 KiB
subtask2 5/5
2 Elfogadva 35ms 20428 KiB
3 Elfogadva 35ms 20672 KiB
4 Elfogadva 35ms 20604 KiB
5 Elfogadva 35ms 20612 KiB
6 Elfogadva 35ms 20820 KiB
7 Elfogadva 35ms 21232 KiB
8 Elfogadva 37ms 21500 KiB
9 Elfogadva 37ms 21448 KiB
10 Elfogadva 37ms 21760 KiB
11 Elfogadva 37ms 21916 KiB
subtask3 5/5
12 Elfogadva 35ms 21828 KiB
13 Elfogadva 34ms 22076 KiB
14 Elfogadva 34ms 21964 KiB
15 Elfogadva 35ms 22064 KiB
16 Elfogadva 37ms 22336 KiB
17 Elfogadva 37ms 22276 KiB
18 Elfogadva 37ms 22588 KiB
19 Elfogadva 35ms 22816 KiB
20 Elfogadva 35ms 22872 KiB
21 Elfogadva 37ms 22832 KiB
subtask4 10/10
22 Elfogadva 56ms 26576 KiB
23 Elfogadva 166ms 31684 KiB
24 Elfogadva 280ms 50860 KiB
25 Elfogadva 398ms 65456 KiB
26 Elfogadva 449ms 72532 KiB
27 Elfogadva 476ms 71908 KiB
subtask5 10/10
28 Elfogadva 68ms 26316 KiB
29 Elfogadva 196ms 30840 KiB
30 Elfogadva 635ms 48492 KiB
31 Elfogadva 1.281s 61428 KiB
32 Elfogadva 1.578s 66192 KiB
33 Elfogadva 1.585s 66196 KiB
subtask6 10/10
34 Elfogadva 37ms 23476 KiB
35 Elfogadva 52ms 27248 KiB
36 Elfogadva 118ms 35648 KiB
37 Elfogadva 243ms 51684 KiB
38 Elfogadva 324ms 67864 KiB
39 Elfogadva 439ms 71264 KiB
40 Elfogadva 342ms 74840 KiB
41 Elfogadva 384ms 71692 KiB
subtask7 15/15
42 Elfogadva 35ms 23620 KiB
43 Elfogadva 54ms 26776 KiB
44 Elfogadva 127ms 34492 KiB
45 Elfogadva 298ms 48496 KiB
46 Elfogadva 513ms 62036 KiB
47 Elfogadva 602ms 66452 KiB
48 Elfogadva 606ms 66560 KiB
49 Elfogadva 600ms 66448 KiB
50 Elfogadva 648ms 66460 KiB
51 Elfogadva 171ms 65064 KiB
52 Elfogadva 234ms 57708 KiB
53 Elfogadva 229ms 63676 KiB
54 Elfogadva 164ms 65152 KiB
55 Elfogadva 250ms 57824 KiB
56 Elfogadva 1.2s 57728 KiB
subtask8 20/20
57 Elfogadva 56ms 27336 KiB
58 Elfogadva 103ms 34960 KiB
59 Elfogadva 204ms 42492 KiB
60 Elfogadva 326ms 53552 KiB
61 Elfogadva 361ms 72480 KiB
62 Elfogadva 356ms 74928 KiB
63 Elfogadva 500ms 71684 KiB
64 Elfogadva 474ms 72284 KiB
65 Elfogadva 216ms 75600 KiB
66 Elfogadva 216ms 75572 KiB
subtask9 25/25
67 Elfogadva 61ms 26844 KiB
68 Elfogadva 119ms 33320 KiB
69 Elfogadva 232ms 40336 KiB
70 Elfogadva 680ms 49184 KiB
71 Elfogadva 606ms 66016 KiB
72 Elfogadva 625ms 66452 KiB
73 Elfogadva 1.231s 66452 KiB
74 Elfogadva 884ms 66624 KiB
75 Elfogadva 754ms 66684 KiB
76 Elfogadva 890ms 66504 KiB
77 Elfogadva 987ms 66592 KiB
78 Elfogadva 796ms 66452 KiB
79 Elfogadva 995ms 66444 KiB
80 Elfogadva 437ms 70116 KiB
81 Elfogadva 470ms 70108 KiB
82 Elfogadva 240ms 75436 KiB
83 Elfogadva 970ms 71264 KiB