46672023-03-30 18:51:29gortomiLegkisebb nem oszthatócpp17Futási hiba 0/1001.508s43472 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva19ms11076 KiB
subtask20/5
2Elfogadva20ms11288 KiB
3Elfogadva19ms11508 KiB
4Futási hiba20ms11724 KiB
5Futási hiba20ms11700 KiB
6Futási hiba20ms12068 KiB
7Elfogadva21ms12160 KiB
8Elfogadva21ms12356 KiB
9Elfogadva20ms12444 KiB
10Elfogadva21ms12528 KiB
11Futási hiba21ms12656 KiB
subtask30/5
12Elfogadva19ms12904 KiB
13Hibás válasz19ms12872 KiB
14Futási hiba20ms12724 KiB
15Futási hiba20ms12844 KiB
16Futási hiba20ms12840 KiB
17Futási hiba20ms12980 KiB
18Futási hiba20ms12984 KiB
19Futási hiba20ms13068 KiB
20Futási hiba23ms13328 KiB
21Futási hiba21ms13196 KiB
subtask40/10
22Futási hiba34ms15336 KiB
23Elfogadva128ms19656 KiB
24Elfogadva200ms28456 KiB
25Elfogadva291ms35452 KiB
26Elfogadva335ms39876 KiB
27Elfogadva344ms39312 KiB
subtask50/10
28Futási hiba43ms15260 KiB
29Futási hiba126ms19152 KiB
30Hibás válasz564ms26156 KiB
31Hibás válasz1.19s31584 KiB
32Hibás válasz1.508s33752 KiB
33Hibás válasz1.506s33752 KiB
subtask60/10
34Futási hiba20ms13832 KiB
35Elfogadva34ms15820 KiB
36Futási hiba67ms20780 KiB
37Elfogadva158ms29472 KiB
38Elfogadva228ms37780 KiB
39Elfogadva256ms38592 KiB
40Elfogadva259ms42108 KiB
41Elfogadva270ms38952 KiB
subtask70/15
42Futási hiba21ms13964 KiB
43Futási hiba34ms15708 KiB
44Futási hiba82ms19884 KiB
45Hibás válasz250ms26640 KiB
46Hibás válasz456ms32356 KiB
47Hibás válasz551ms34164 KiB
48Hibás válasz551ms34208 KiB
49Hibás válasz541ms34112 KiB
50Hibás válasz596ms34328 KiB
51Hibás válasz128ms38060 KiB
52Elfogadva162ms30828 KiB
53Elfogadva159ms36804 KiB
54Hibás válasz128ms38220 KiB
55Elfogadva160ms30832 KiB
56Hibás válasz1.105s30836 KiB
subtask80/20
57Elfogadva35ms16404 KiB
58Futási hiba65ms21440 KiB
59Hibás válasz149ms25856 KiB
60Elfogadva252ms31600 KiB
61Hibás válasz259ms40708 KiB
62Elfogadva259ms42920 KiB
63Elfogadva375ms39752 KiB
64Elfogadva337ms40400 KiB
65Elfogadva175ms43472 KiB
66Elfogadva171ms43464 KiB
subtask90/25
67Futási hiba39ms16112 KiB
68Futási hiba75ms19612 KiB
69Hibás válasz193ms23456 KiB
70Hibás válasz619ms27152 KiB
71Hibás válasz532ms34228 KiB
72Hibás válasz550ms34520 KiB
73Hibás válasz1.172s34500 KiB
74Hibás válasz813ms34500 KiB
75Hibás válasz669ms34392 KiB
76Hibás válasz832ms34428 KiB
77Hibás válasz902ms34464 KiB
78Hibás válasz745ms34380 KiB
79Hibás válasz915ms34392 KiB
80Elfogadva367ms38072 KiB
81Elfogadva400ms38036 KiB
82Elfogadva168ms43364 KiB
83Hibás válasz847ms39204 KiB