4626 2023. 03. 30 12:55:30 gortomi Legkisebb nem osztható cpp17 Hibás válasz 10/100 1.564s 42128 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";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 17ms 11076 KiB
subtask2 0/5
2 Hibás válasz 17ms 11292 KiB
3 Hibás válasz 17ms 11484 KiB
4 Hibás válasz 17ms 11716 KiB
5 Elfogadva 17ms 11924 KiB
6 Elfogadva 18ms 12268 KiB
7 Elfogadva 18ms 12612 KiB
8 Elfogadva 18ms 12684 KiB
9 Elfogadva 18ms 12708 KiB
10 Hibás válasz 19ms 12796 KiB
11 Hibás válasz 19ms 12804 KiB
subtask3 0/5
12 Elfogadva 17ms 12780 KiB
13 Hibás válasz 17ms 12868 KiB
14 Hibás válasz 17ms 13132 KiB
15 Elfogadva 17ms 13216 KiB
16 Elfogadva 18ms 13376 KiB
17 Elfogadva 18ms 13596 KiB
18 Elfogadva 18ms 13612 KiB
19 Elfogadva 18ms 13400 KiB
20 Hibás válasz 19ms 13400 KiB
21 Hibás válasz 19ms 13588 KiB
subtask4 0/10
22 Hibás válasz 35ms 15200 KiB
23 Hibás válasz 136ms 19248 KiB
24 Elfogadva 248ms 27652 KiB
25 Hibás válasz 402ms 34288 KiB
26 Hibás válasz 569ms 38584 KiB
27 Hibás válasz 537ms 38028 KiB
subtask5 0/10
28 Hibás válasz 50ms 15084 KiB
29 Hibás válasz 181ms 18200 KiB
30 Hibás válasz 620ms 25176 KiB
31 Hibás válasz 1.223s 30252 KiB
32 Hibás válasz 1.536s 32128 KiB
33 Hibás válasz 1.564s 32276 KiB
subtask6 10/10
34 Elfogadva 18ms 14096 KiB
35 Elfogadva 32ms 16052 KiB
36 Elfogadva 87ms 20252 KiB
37 Elfogadva 193ms 28484 KiB
38 Elfogadva 289ms 36868 KiB
39 Elfogadva 358ms 37376 KiB
40 Elfogadva 356ms 40612 KiB
41 Elfogadva 372ms 37500 KiB
subtask7 0/15
42 Elfogadva 18ms 14196 KiB
43 Elfogadva 35ms 15532 KiB
44 Elfogadva 104ms 19388 KiB
45 Elfogadva 264ms 25584 KiB
46 Elfogadva 485ms 30964 KiB
47 Elfogadva 560ms 32688 KiB
48 Elfogadva 561ms 32680 KiB
49 Elfogadva 552ms 32672 KiB
50 Hibás válasz 620ms 32700 KiB
51 Hibás válasz 153ms 36540 KiB
52 Hibás válasz 156ms 29176 KiB
53 Hibás válasz 180ms 35344 KiB
54 Hibás válasz 150ms 36628 KiB
55 Hibás válasz 156ms 29424 KiB
56 Elfogadva 1.511s 29424 KiB
subtask8 0/20
57 Hibás válasz 37ms 16044 KiB
58 Elfogadva 87ms 20712 KiB
59 Hibás válasz 165ms 24780 KiB
60 Hibás válasz 488ms 30504 KiB
61 Elfogadva 435ms 39384 KiB
62 Elfogadva 361ms 41664 KiB
63 Hibás válasz 568ms 38052 KiB
64 Hibás válasz 556ms 38880 KiB
65 Hibás válasz 174ms 42016 KiB
66 Hibás válasz 165ms 42128 KiB
subtask9 0/25
67 Hibás válasz 43ms 15752 KiB
68 Elfogadva 92ms 18900 KiB
69 Hibás válasz 206ms 22252 KiB
70 Hibás válasz 644ms 26056 KiB
71 Elfogadva 537ms 32540 KiB
72 Elfogadva 558ms 32692 KiB
73 Hibás válasz 1.182s 32668 KiB
74 Hibás válasz 837ms 32676 KiB
75 Hibás válasz 671ms 32668 KiB
76 Hibás válasz 838ms 32760 KiB
77 Hibás válasz 893ms 32676 KiB
78 Hibás válasz 742ms 32700 KiB
79 Hibás válasz 912ms 32676 KiB
80 Elfogadva 374ms 36392 KiB
81 Elfogadva 405ms 36428 KiB
82 Hibás válasz 179ms 41740 KiB
83 Hibás válasz 976ms 37852 KiB