4680 2023. 03. 31 08:29:19 gortomi Legkisebb nem osztható cpp17 Hibás válasz 85/100 1.585s 67000 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(1e6 + 1, 1);
    vector<int> pl(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 <= 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, 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 18ms 11148 KiB
subtask2 5/5
2 Elfogadva 17ms 11364 KiB
3 Elfogadva 18ms 11584 KiB
4 Elfogadva 18ms 11544 KiB
5 Elfogadva 19ms 11812 KiB
6 Elfogadva 18ms 12148 KiB
7 Elfogadva 19ms 12404 KiB
8 Elfogadva 18ms 12556 KiB
9 Elfogadva 19ms 12712 KiB
10 Elfogadva 19ms 12988 KiB
11 Elfogadva 19ms 13240 KiB
subtask3 5/5
12 Elfogadva 17ms 12964 KiB
13 Elfogadva 18ms 13140 KiB
14 Elfogadva 18ms 13368 KiB
15 Elfogadva 19ms 13564 KiB
16 Elfogadva 19ms 13536 KiB
17 Elfogadva 19ms 13588 KiB
18 Elfogadva 20ms 14032 KiB
19 Elfogadva 19ms 14124 KiB
20 Elfogadva 20ms 13988 KiB
21 Elfogadva 20ms 13984 KiB
subtask4 10/10
22 Elfogadva 41ms 17916 KiB
23 Elfogadva 155ms 23044 KiB
24 Elfogadva 277ms 41632 KiB
25 Elfogadva 402ms 56228 KiB
26 Elfogadva 495ms 63468 KiB
27 Elfogadva 504ms 62904 KiB
subtask5 10/10
28 Elfogadva 52ms 17400 KiB
29 Elfogadva 178ms 22268 KiB
30 Elfogadva 610ms 39616 KiB
31 Elfogadva 1.254s 52804 KiB
32 Elfogadva 1.562s 57636 KiB
33 Elfogadva 1.585s 57648 KiB
subtask6 10/10
34 Elfogadva 19ms 14564 KiB
35 Elfogadva 37ms 18648 KiB
36 Elfogadva 98ms 27036 KiB
37 Elfogadva 228ms 42944 KiB
38 Elfogadva 307ms 59124 KiB
39 Elfogadva 386ms 62644 KiB
40 Elfogadva 347ms 66160 KiB
41 Elfogadva 395ms 62920 KiB
subtask7 0/15
42 Elfogadva 20ms 14552 KiB
43 Elfogadva 39ms 18032 KiB
44 Elfogadva 111ms 25728 KiB
45 Elfogadva 289ms 39940 KiB
46 Elfogadva 513ms 53392 KiB
47 Elfogadva 606ms 57772 KiB
48 Elfogadva 609ms 57860 KiB
49 Elfogadva 601ms 57840 KiB
50 Elfogadva 651ms 57760 KiB
51 Hibás válasz 152ms 56412 KiB
52 Elfogadva 232ms 49088 KiB
53 Elfogadva 214ms 55152 KiB
54 Hibás válasz 152ms 56644 KiB
55 Elfogadva 217ms 49308 KiB
56 Elfogadva 1.182s 49376 KiB
subtask8 20/20
57 Elfogadva 37ms 18784 KiB
58 Elfogadva 87ms 26452 KiB
59 Elfogadva 189ms 33896 KiB
60 Elfogadva 308ms 44888 KiB
61 Elfogadva 345ms 64016 KiB
62 Elfogadva 337ms 66552 KiB
63 Elfogadva 504ms 63308 KiB
64 Elfogadva 430ms 64000 KiB
65 Elfogadva 206ms 67000 KiB
66 Elfogadva 199ms 66976 KiB
subtask9 25/25
67 Elfogadva 45ms 18200 KiB
68 Elfogadva 101ms 24700 KiB
69 Elfogadva 217ms 31620 KiB
70 Elfogadva 670ms 40536 KiB
71 Elfogadva 587ms 57484 KiB
72 Elfogadva 610ms 57920 KiB
73 Elfogadva 1.21s 57884 KiB
74 Elfogadva 875ms 57912 KiB
75 Elfogadva 737ms 57980 KiB
76 Elfogadva 897ms 57980 KiB
77 Elfogadva 954ms 57912 KiB
78 Elfogadva 796ms 57900 KiB
79 Elfogadva 957ms 57900 KiB
80 Elfogadva 421ms 61660 KiB
81 Elfogadva 456ms 61652 KiB
82 Elfogadva 216ms 66956 KiB
83 Elfogadva 953ms 62828 KiB