46312023-03-30 13:12:59gortomiLegkisebb nem oszthatócpp17Hibás válasz 45/1001.504s42072 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva18ms10948 KiB
subtask25/5
2Elfogadva17ms11164 KiB
3Elfogadva18ms11384 KiB
4Elfogadva17ms11352 KiB
5Elfogadva17ms11688 KiB
6Elfogadva18ms11992 KiB
7Elfogadva18ms12088 KiB
8Elfogadva18ms12308 KiB
9Elfogadva18ms12548 KiB
10Elfogadva18ms12492 KiB
11Elfogadva19ms12496 KiB
subtask30/5
12Elfogadva17ms12336 KiB
13Elfogadva17ms12696 KiB
14Hibás válasz17ms12796 KiB
15Elfogadva18ms12944 KiB
16Elfogadva18ms12800 KiB
17Elfogadva18ms13284 KiB
18Elfogadva19ms13240 KiB
19Elfogadva18ms13204 KiB
20Hibás válasz19ms13332 KiB
21Hibás válasz19ms13212 KiB
subtask410/10
22Elfogadva35ms14696 KiB
23Elfogadva136ms18652 KiB
24Elfogadva203ms27408 KiB
25Elfogadva294ms34148 KiB
26Elfogadva330ms38220 KiB
27Elfogadva330ms37760 KiB
subtask50/10
28Hibás válasz46ms14940 KiB
29Hibás válasz165ms18036 KiB
30Hibás válasz569ms25076 KiB
31Hibás válasz1.19s30228 KiB
32Hibás válasz1.496s32192 KiB
33Hibás válasz1.504s32196 KiB
subtask610/10
34Elfogadva18ms13976 KiB
35Elfogadva32ms15944 KiB
36Elfogadva79ms20048 KiB
37Elfogadva164ms28272 KiB
38Elfogadva232ms36556 KiB
39Elfogadva266ms37280 KiB
40Elfogadva266ms40548 KiB
41Elfogadva275ms37412 KiB
subtask70/15
42Elfogadva18ms13992 KiB
43Elfogadva35ms15168 KiB
44Elfogadva97ms18896 KiB
45Elfogadva252ms25208 KiB
46Elfogadva455ms30452 KiB
47Elfogadva547ms32228 KiB
48Elfogadva544ms32500 KiB
49Elfogadva537ms32392 KiB
50Hibás válasz584ms32452 KiB
51Hibás válasz119ms36588 KiB
52Elfogadva152ms29248 KiB
53Elfogadva155ms35272 KiB
54Hibás válasz119ms36472 KiB
55Elfogadva152ms29120 KiB
56Elfogadva1.1s29176 KiB
subtask820/20
57Elfogadva34ms15940 KiB
58Elfogadva78ms20764 KiB
59Elfogadva150ms24768 KiB
60Elfogadva256ms30432 KiB
61Elfogadva257ms39264 KiB
62Elfogadva261ms41424 KiB
63Elfogadva379ms37912 KiB
64Elfogadva333ms38760 KiB
65Elfogadva173ms42072 KiB
66Elfogadva166ms41984 KiB
subtask90/25
67Hibás válasz41ms15584 KiB
68Elfogadva90ms18684 KiB
69Hibás válasz194ms22216 KiB
70Hibás válasz620ms26032 KiB
71Elfogadva523ms32484 KiB
72Elfogadva542ms32640 KiB
73Hibás válasz1.148s32616 KiB
74Hibás válasz810ms32628 KiB
75Hibás válasz669ms32676 KiB
76Hibás válasz828ms32624 KiB
77Hibás válasz892ms32752 KiB
78Hibás válasz736ms32732 KiB
79Hibás válasz903ms32624 KiB
80Elfogadva367ms36284 KiB
81Elfogadva398ms36284 KiB
82Elfogadva175ms41636 KiB
83Elfogadva833ms37732 KiB