4668 2023. 03. 30 18:53:36 gortomi Legkisebb nem osztható cpp17 Hibás válasz 45/100 1.511s 43488 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[path[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[path[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 5/5
2 Elfogadva 20ms 11292 KiB
3 Elfogadva 20ms 11788 KiB
4 Elfogadva 19ms 11880 KiB
5 Elfogadva 20ms 12100 KiB
6 Elfogadva 20ms 12556 KiB
7 Elfogadva 20ms 12660 KiB
8 Elfogadva 21ms 12636 KiB
9 Elfogadva 20ms 12800 KiB
10 Elfogadva 20ms 13004 KiB
11 Elfogadva 20ms 13272 KiB
subtask3 0/5
12 Elfogadva 19ms 13304 KiB
13 Elfogadva 19ms 13252 KiB
14 Hibás válasz 20ms 13480 KiB
15 Elfogadva 20ms 13468 KiB
16 Elfogadva 20ms 13352 KiB
17 Elfogadva 21ms 13436 KiB
18 Elfogadva 21ms 13488 KiB
19 Elfogadva 21ms 13660 KiB
20 Hibás válasz 21ms 13572 KiB
21 Hibás válasz 21ms 13572 KiB
subtask4 10/10
22 Elfogadva 35ms 15416 KiB
23 Elfogadva 133ms 19804 KiB
24 Elfogadva 207ms 28396 KiB
25 Elfogadva 296ms 35404 KiB
26 Elfogadva 340ms 39820 KiB
27 Elfogadva 342ms 39464 KiB
subtask5 0/10
28 Hibás válasz 48ms 15296 KiB
29 Hibás válasz 158ms 19236 KiB
30 Hibás válasz 566ms 26484 KiB
31 Hibás válasz 1.195s 31896 KiB
32 Hibás válasz 1.511s 33976 KiB
33 Hibás válasz 1.511s 34032 KiB
subtask6 10/10
34 Elfogadva 21ms 14216 KiB
35 Elfogadva 32ms 16188 KiB
36 Elfogadva 81ms 21132 KiB
37 Elfogadva 164ms 29924 KiB
38 Elfogadva 238ms 38196 KiB
39 Elfogadva 263ms 39052 KiB
40 Elfogadva 263ms 42452 KiB
41 Elfogadva 280ms 39496 KiB
subtask7 0/15
42 Elfogadva 21ms 14384 KiB
43 Elfogadva 37ms 15768 KiB
44 Elfogadva 97ms 19724 KiB
45 Elfogadva 254ms 26904 KiB
46 Elfogadva 465ms 32512 KiB
47 Elfogadva 555ms 34440 KiB
48 Elfogadva 551ms 34404 KiB
49 Elfogadva 545ms 34316 KiB
50 Hibás válasz 597ms 34284 KiB
51 Hibás válasz 130ms 37972 KiB
52 Elfogadva 165ms 30660 KiB
53 Elfogadva 164ms 36464 KiB
54 Hibás válasz 131ms 37964 KiB
55 Elfogadva 168ms 30596 KiB
56 Elfogadva 1.113s 30548 KiB
subtask8 20/20
57 Elfogadva 35ms 16116 KiB
58 Elfogadva 76ms 21084 KiB
59 Elfogadva 158ms 25664 KiB
60 Elfogadva 263ms 31484 KiB
61 Elfogadva 272ms 40692 KiB
62 Elfogadva 273ms 42912 KiB
63 Elfogadva 397ms 39664 KiB
64 Elfogadva 342ms 40228 KiB
65 Elfogadva 179ms 43488 KiB
66 Elfogadva 175ms 43452 KiB
subtask9 0/25
67 Hibás válasz 43ms 15804 KiB
68 Elfogadva 90ms 19348 KiB
69 Hibás válasz 194ms 23448 KiB
70 Hibás válasz 624ms 27284 KiB
71 Elfogadva 529ms 34244 KiB
72 Elfogadva 546ms 34424 KiB
73 Hibás válasz 1.166s 34412 KiB
74 Hibás válasz 822ms 34416 KiB
75 Hibás válasz 675ms 34380 KiB
76 Hibás válasz 837ms 34376 KiB
77 Hibás válasz 906ms 34428 KiB
78 Hibás válasz 749ms 34388 KiB
79 Hibás válasz 925ms 34412 KiB
80 Elfogadva 374ms 38024 KiB
81 Elfogadva 404ms 38040 KiB
82 Elfogadva 175ms 43356 KiB
83 Elfogadva 852ms 39188 KiB