46262023-03-30 12:55:30gortomiLegkisebb nem oszthatócpp17Hibás válasz 10/1001.564s42128 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;
        que[i].l = r[x];
        que[i].r = l[y];
        if(que[i].l > que[i].r)
        {
            que[i].l = r[y];
            que[i].r = l[x];
        }
        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
1Elfogadva17ms11076 KiB
subtask20/5
2Hibás válasz17ms11292 KiB
3Hibás válasz17ms11484 KiB
4Hibás válasz17ms11716 KiB
5Elfogadva17ms11924 KiB
6Elfogadva18ms12268 KiB
7Elfogadva18ms12612 KiB
8Elfogadva18ms12684 KiB
9Elfogadva18ms12708 KiB
10Hibás válasz19ms12796 KiB
11Hibás válasz19ms12804 KiB
subtask30/5
12Elfogadva17ms12780 KiB
13Hibás válasz17ms12868 KiB
14Hibás válasz17ms13132 KiB
15Elfogadva17ms13216 KiB
16Elfogadva18ms13376 KiB
17Elfogadva18ms13596 KiB
18Elfogadva18ms13612 KiB
19Elfogadva18ms13400 KiB
20Hibás válasz19ms13400 KiB
21Hibás válasz19ms13588 KiB
subtask40/10
22Hibás válasz35ms15200 KiB
23Hibás válasz136ms19248 KiB
24Elfogadva248ms27652 KiB
25Hibás válasz402ms34288 KiB
26Hibás válasz569ms38584 KiB
27Hibás válasz537ms38028 KiB
subtask50/10
28Hibás válasz50ms15084 KiB
29Hibás válasz181ms18200 KiB
30Hibás válasz620ms25176 KiB
31Hibás válasz1.223s30252 KiB
32Hibás válasz1.536s32128 KiB
33Hibás válasz1.564s32276 KiB
subtask610/10
34Elfogadva18ms14096 KiB
35Elfogadva32ms16052 KiB
36Elfogadva87ms20252 KiB
37Elfogadva193ms28484 KiB
38Elfogadva289ms36868 KiB
39Elfogadva358ms37376 KiB
40Elfogadva356ms40612 KiB
41Elfogadva372ms37500 KiB
subtask70/15
42Elfogadva18ms14196 KiB
43Elfogadva35ms15532 KiB
44Elfogadva104ms19388 KiB
45Elfogadva264ms25584 KiB
46Elfogadva485ms30964 KiB
47Elfogadva560ms32688 KiB
48Elfogadva561ms32680 KiB
49Elfogadva552ms32672 KiB
50Hibás válasz620ms32700 KiB
51Hibás válasz153ms36540 KiB
52Hibás válasz156ms29176 KiB
53Hibás válasz180ms35344 KiB
54Hibás válasz150ms36628 KiB
55Hibás válasz156ms29424 KiB
56Elfogadva1.511s29424 KiB
subtask80/20
57Hibás válasz37ms16044 KiB
58Elfogadva87ms20712 KiB
59Hibás válasz165ms24780 KiB
60Hibás válasz488ms30504 KiB
61Elfogadva435ms39384 KiB
62Elfogadva361ms41664 KiB
63Hibás válasz568ms38052 KiB
64Hibás válasz556ms38880 KiB
65Hibás válasz174ms42016 KiB
66Hibás válasz165ms42128 KiB
subtask90/25
67Hibás válasz43ms15752 KiB
68Elfogadva92ms18900 KiB
69Hibás válasz206ms22252 KiB
70Hibás válasz644ms26056 KiB
71Elfogadva537ms32540 KiB
72Elfogadva558ms32692 KiB
73Hibás válasz1.182s32668 KiB
74Hibás válasz837ms32676 KiB
75Hibás válasz671ms32668 KiB
76Hibás válasz838ms32760 KiB
77Hibás válasz893ms32676 KiB
78Hibás válasz742ms32700 KiB
79Hibás válasz912ms32676 KiB
80Elfogadva374ms36392 KiB
81Elfogadva405ms36428 KiB
82Hibás válasz179ms41740 KiB
83Hibás válasz976ms37852 KiB