4667 2023. 03. 30 18:51:29 gortomi Legkisebb nem osztható cpp17 Futási hiba 0/100 1.508s 43472 KiB 
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > g;
int tim = 0;
vector<int> l, r, par;
void dfs(int n, int p)
{
    par[n] = p;
    l[n] = tim++;
    for(auto x : g[n]) if(x != p) dfs(x, n);
    r[n] = tim++;
}
struct val
{
    int l, r, ind, ty;
};
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);
    par.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;
        if(l[x] < l[y] && r[x] < r[y])
        {
            que[i].l = r[x];
            que[i].r = l[y];
            que[i].ty = 1;
        }
        else if(l[x] > l[y] && r[x] > r[y])
        {
            que[i].l = r[y];
            que[i].r = l[x];
            que[i].ty = 1;
        }
        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].ty = 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]--;
            }
        }
        if(que[i].ty == 1)
        {
            int x = v[par[que[i].l]];
            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(que[i].ty == 1)
        {
            int x = v[par[que[i].l]];
            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 19ms 11076 KiB
subtask2 0/5
2 Elfogadva 20ms 11288 KiB
3 Elfogadva 19ms 11508 KiB
4 Futási hiba 20ms 11724 KiB
5 Futási hiba 20ms 11700 KiB
6 Futási hiba 20ms 12068 KiB
7 Elfogadva 21ms 12160 KiB
8 Elfogadva 21ms 12356 KiB
9 Elfogadva 20ms 12444 KiB
10 Elfogadva 21ms 12528 KiB
11 Futási hiba 21ms 12656 KiB
subtask3 0/5
12 Elfogadva 19ms 12904 KiB
13 Hibás válasz 19ms 12872 KiB
14 Futási hiba 20ms 12724 KiB
15 Futási hiba 20ms 12844 KiB
16 Futási hiba 20ms 12840 KiB
17 Futási hiba 20ms 12980 KiB
18 Futási hiba 20ms 12984 KiB
19 Futási hiba 20ms 13068 KiB
20 Futási hiba 23ms 13328 KiB
21 Futási hiba 21ms 13196 KiB
subtask4 0/10
22 Futási hiba 34ms 15336 KiB
23 Elfogadva 128ms 19656 KiB
24 Elfogadva 200ms 28456 KiB
25 Elfogadva 291ms 35452 KiB
26 Elfogadva 335ms 39876 KiB
27 Elfogadva 344ms 39312 KiB
subtask5 0/10
28 Futási hiba 43ms 15260 KiB
29 Futási hiba 126ms 19152 KiB
30 Hibás válasz 564ms 26156 KiB
31 Hibás válasz 1.19s 31584 KiB
32 Hibás válasz 1.508s 33752 KiB
33 Hibás válasz 1.506s 33752 KiB
subtask6 0/10
34 Futási hiba 20ms 13832 KiB
35 Elfogadva 34ms 15820 KiB
36 Futási hiba 67ms 20780 KiB
37 Elfogadva 158ms 29472 KiB
38 Elfogadva 228ms 37780 KiB
39 Elfogadva 256ms 38592 KiB
40 Elfogadva 259ms 42108 KiB
41 Elfogadva 270ms 38952 KiB
subtask7 0/15
42 Futási hiba 21ms 13964 KiB
43 Futási hiba 34ms 15708 KiB
44 Futási hiba 82ms 19884 KiB
45 Hibás válasz 250ms 26640 KiB
46 Hibás válasz 456ms 32356 KiB
47 Hibás válasz 551ms 34164 KiB
48 Hibás válasz 551ms 34208 KiB
49 Hibás válasz 541ms 34112 KiB
50 Hibás válasz 596ms 34328 KiB
51 Hibás válasz 128ms 38060 KiB
52 Elfogadva 162ms 30828 KiB
53 Elfogadva 159ms 36804 KiB
54 Hibás válasz 128ms 38220 KiB
55 Elfogadva 160ms 30832 KiB
56 Hibás válasz 1.105s 30836 KiB
subtask8 0/20
57 Elfogadva 35ms 16404 KiB
58 Futási hiba 65ms 21440 KiB
59 Hibás válasz 149ms 25856 KiB
60 Elfogadva 252ms 31600 KiB
61 Hibás válasz 259ms 40708 KiB
62 Elfogadva 259ms 42920 KiB
63 Elfogadva 375ms 39752 KiB
64 Elfogadva 337ms 40400 KiB
65 Elfogadva 175ms 43472 KiB
66 Elfogadva 171ms 43464 KiB
subtask9 0/25
67 Futási hiba 39ms 16112 KiB
68 Futási hiba 75ms 19612 KiB
69 Hibás válasz 193ms 23456 KiB
70 Hibás válasz 619ms 27152 KiB
71 Hibás válasz 532ms 34228 KiB
72 Hibás válasz 550ms 34520 KiB
73 Hibás válasz 1.172s 34500 KiB
74 Hibás válasz 813ms 34500 KiB
75 Hibás válasz 669ms 34392 KiB
76 Hibás válasz 832ms 34428 KiB
77 Hibás válasz 902ms 34464 KiB
78 Hibás válasz 745ms 34380 KiB
79 Hibás válasz 915ms 34392 KiB
80 Elfogadva 367ms 38072 KiB
81 Elfogadva 400ms 38036 KiB
82 Elfogadva 168ms 43364 KiB
83 Hibás válasz 847ms 39204 KiB