4631 2023. 03. 30 13:12:59 gortomi Legkisebb nem osztható cpp17 Hibás válasz 45/100 1.504s 42072 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;
        if(l[x] < l[y] && r[x] < r[y])
        {
            que[i].l = r[x];
            que[i].r = l[y];
        }
        else if(l[x] > l[y] && r[x] > r[y])
        {
            que[i].l = r[y];
            que[i].r = l[x];
        }
        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].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 18ms 10948 KiB
subtask2 5/5
2 Elfogadva 17ms 11164 KiB
3 Elfogadva 18ms 11384 KiB
4 Elfogadva 17ms 11352 KiB
5 Elfogadva 17ms 11688 KiB
6 Elfogadva 18ms 11992 KiB
7 Elfogadva 18ms 12088 KiB
8 Elfogadva 18ms 12308 KiB
9 Elfogadva 18ms 12548 KiB
10 Elfogadva 18ms 12492 KiB
11 Elfogadva 19ms 12496 KiB
subtask3 0/5
12 Elfogadva 17ms 12336 KiB
13 Elfogadva 17ms 12696 KiB
14 Hibás válasz 17ms 12796 KiB
15 Elfogadva 18ms 12944 KiB
16 Elfogadva 18ms 12800 KiB
17 Elfogadva 18ms 13284 KiB
18 Elfogadva 19ms 13240 KiB
19 Elfogadva 18ms 13204 KiB
20 Hibás válasz 19ms 13332 KiB
21 Hibás válasz 19ms 13212 KiB
subtask4 10/10
22 Elfogadva 35ms 14696 KiB
23 Elfogadva 136ms 18652 KiB
24 Elfogadva 203ms 27408 KiB
25 Elfogadva 294ms 34148 KiB
26 Elfogadva 330ms 38220 KiB
27 Elfogadva 330ms 37760 KiB
subtask5 0/10
28 Hibás válasz 46ms 14940 KiB
29 Hibás válasz 165ms 18036 KiB
30 Hibás válasz 569ms 25076 KiB
31 Hibás válasz 1.19s 30228 KiB
32 Hibás válasz 1.496s 32192 KiB
33 Hibás válasz 1.504s 32196 KiB
subtask6 10/10
34 Elfogadva 18ms 13976 KiB
35 Elfogadva 32ms 15944 KiB
36 Elfogadva 79ms 20048 KiB
37 Elfogadva 164ms 28272 KiB
38 Elfogadva 232ms 36556 KiB
39 Elfogadva 266ms 37280 KiB
40 Elfogadva 266ms 40548 KiB
41 Elfogadva 275ms 37412 KiB
subtask7 0/15
42 Elfogadva 18ms 13992 KiB
43 Elfogadva 35ms 15168 KiB
44 Elfogadva 97ms 18896 KiB
45 Elfogadva 252ms 25208 KiB
46 Elfogadva 455ms 30452 KiB
47 Elfogadva 547ms 32228 KiB
48 Elfogadva 544ms 32500 KiB
49 Elfogadva 537ms 32392 KiB
50 Hibás válasz 584ms 32452 KiB
51 Hibás válasz 119ms 36588 KiB
52 Elfogadva 152ms 29248 KiB
53 Elfogadva 155ms 35272 KiB
54 Hibás válasz 119ms 36472 KiB
55 Elfogadva 152ms 29120 KiB
56 Elfogadva 1.1s 29176 KiB
subtask8 20/20
57 Elfogadva 34ms 15940 KiB
58 Elfogadva 78ms 20764 KiB
59 Elfogadva 150ms 24768 KiB
60 Elfogadva 256ms 30432 KiB
61 Elfogadva 257ms 39264 KiB
62 Elfogadva 261ms 41424 KiB
63 Elfogadva 379ms 37912 KiB
64 Elfogadva 333ms 38760 KiB
65 Elfogadva 173ms 42072 KiB
66 Elfogadva 166ms 41984 KiB
subtask9 0/25
67 Hibás válasz 41ms 15584 KiB
68 Elfogadva 90ms 18684 KiB
69 Hibás válasz 194ms 22216 KiB
70 Hibás válasz 620ms 26032 KiB
71 Elfogadva 523ms 32484 KiB
72 Elfogadva 542ms 32640 KiB
73 Hibás válasz 1.148s 32616 KiB
74 Hibás válasz 810ms 32628 KiB
75 Hibás válasz 669ms 32676 KiB
76 Hibás válasz 828ms 32624 KiB
77 Hibás válasz 892ms 32752 KiB
78 Hibás válasz 736ms 32732 KiB
79 Hibás válasz 903ms 32624 KiB
80 Elfogadva 367ms 36284 KiB
81 Elfogadva 398ms 36284 KiB
82 Elfogadva 175ms 41636 KiB
83 Elfogadva 833ms 37732 KiB