Submission #4,682

2023-03-31 08:47:00

cpp17

Accepted 100/100

1.585s

75600 KiB

#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > g, par;
int tim = 0;
vector<int> l, r, d;
void dfs(int n, int p)
{
    par[n][0] = p;
    d[n] = d[p] + 1;
    l[n] = tim++;
    for(int i = 1; i <= 19; i++)
    {
        par[n][i] = par[par[n][i - 1]][i - 1];
    }
    for(auto x : g[n]) if(x != p) dfs(x, n);
    r[n] = tim++;
}
struct val
{
    int l, r, ind, lca;
};
bool comp(val a, val b)
{
    return a.l / 350 < b.l / 350 || (a.l / 350 == b.l / 350 && a.r < b.r);
}
int calc(int a, int b)
{
    if(d[a] < d[b]) swap(a, b);
    int v = d[a] - d[b];
    for(int i = 0; i <= 19; i++)
    {
        if((v >> i) & 1) a = par[a][i];
    }
    for(int i = 19; i >= 0; i--)
    {
        if(par[a][i] != par[b][i])
        {
            a = par[a][i];
            b = par[b][i];
        }
    }
    return par[a][0];
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> prim;
    vector<bool> ip(2 * 1e6 + 1, 1);
    vector<int> pl(2 * 1e6 + 1);
    g.resize(n + 1);
    d.resize(n + 1);
    l.resize(n + 1);
    r.resize(n + 1);
    par.resize(n + 1, vector<int>(20));
    for(int i = 2; i <= 2 * 1e6; i++)
    {
        if(ip[i])
        {
            pl[i] = prim.size();
            prim.push_back(i);
            for(int j = 2 * i; j <= 2 * 1e6; j += i)
            {
                ip[j] = 0;
            }
        }
    }
    vector<int> v(n + 1, 2 * 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, 1);
    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, 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].lca = calc(x, y);
        }
        else if(l[x] > l[y] && r[x] > r[y])
        {
            que[i].l = r[y];
            que[i].r = l[x];
            que[i].lca = calc(x, y);
        }
        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].lca = 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]--;
            }
        }
        int x = v[que[i].lca];
        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(x <= n)
        {
            db[x]--;
            if(db[x] == 0) sq[x / b]--;
        }
    }
    for(auto x : ans) cout << prim[x] << "\n";
}

	Sum	Test	Verdict	Time	Memory
subtask1	0/0
subtask1	0/0	1	Accepted	35ms	20048 KiB
subtask2	5/5
		2	Accepted	35ms	20428 KiB
		3	Accepted	35ms	20672 KiB
		4	Accepted	35ms	20604 KiB
		5	Accepted	35ms	20612 KiB
		6	Accepted	35ms	20820 KiB
		7	Accepted	35ms	21232 KiB
		8	Accepted	37ms	21500 KiB
		9	Accepted	37ms	21448 KiB
		10	Accepted	37ms	21760 KiB
		11	Accepted	37ms	21916 KiB
subtask3	5/5
		12	Accepted	35ms	21828 KiB
		13	Accepted	34ms	22076 KiB
		14	Accepted	34ms	21964 KiB
		15	Accepted	35ms	22064 KiB
		16	Accepted	37ms	22336 KiB
		17	Accepted	37ms	22276 KiB
		18	Accepted	37ms	22588 KiB
		19	Accepted	35ms	22816 KiB
		20	Accepted	35ms	22872 KiB
		21	Accepted	37ms	22832 KiB
subtask4	10/10
		22	Accepted	56ms	26576 KiB
		23	Accepted	166ms	31684 KiB
		24	Accepted	280ms	50860 KiB
		25	Accepted	398ms	65456 KiB
		26	Accepted	449ms	72532 KiB
		27	Accepted	476ms	71908 KiB
subtask5	10/10
		28	Accepted	68ms	26316 KiB
		29	Accepted	196ms	30840 KiB
		30	Accepted	635ms	48492 KiB
		31	Accepted	1.281s	61428 KiB
		32	Accepted	1.578s	66192 KiB
		33	Accepted	1.585s	66196 KiB
subtask6	10/10
		34	Accepted	37ms	23476 KiB
		35	Accepted	52ms	27248 KiB
		36	Accepted	118ms	35648 KiB
		37	Accepted	243ms	51684 KiB
		38	Accepted	324ms	67864 KiB
		39	Accepted	439ms	71264 KiB
		40	Accepted	342ms	74840 KiB
		41	Accepted	384ms	71692 KiB
subtask7	15/15
		42	Accepted	35ms	23620 KiB
		43	Accepted	54ms	26776 KiB
		44	Accepted	127ms	34492 KiB
		45	Accepted	298ms	48496 KiB
		46	Accepted	513ms	62036 KiB
		47	Accepted	602ms	66452 KiB
		48	Accepted	606ms	66560 KiB
		49	Accepted	600ms	66448 KiB
		50	Accepted	648ms	66460 KiB
		51	Accepted	171ms	65064 KiB
		52	Accepted	234ms	57708 KiB
		53	Accepted	229ms	63676 KiB
		54	Accepted	164ms	65152 KiB
		55	Accepted	250ms	57824 KiB
		56	Accepted	1.2s	57728 KiB
subtask8	20/20
		57	Accepted	56ms	27336 KiB
		58	Accepted	103ms	34960 KiB
		59	Accepted	204ms	42492 KiB
		60	Accepted	326ms	53552 KiB
		61	Accepted	361ms	72480 KiB
		62	Accepted	356ms	74928 KiB
		63	Accepted	500ms	71684 KiB
		64	Accepted	474ms	72284 KiB
		65	Accepted	216ms	75600 KiB
		66	Accepted	216ms	75572 KiB
subtask9	25/25
		67	Accepted	61ms	26844 KiB
		68	Accepted	119ms	33320 KiB
		69	Accepted	232ms	40336 KiB
		70	Accepted	680ms	49184 KiB
		71	Accepted	606ms	66016 KiB
		72	Accepted	625ms	66452 KiB
		73	Accepted	1.231s	66452 KiB
		74	Accepted	884ms	66624 KiB
		75	Accepted	754ms	66684 KiB
		76	Accepted	890ms	66504 KiB
		77	Accepted	987ms	66592 KiB
		78	Accepted	796ms	66452 KiB
		79	Accepted	995ms	66444 KiB
		80	Accepted	437ms	70116 KiB
		81	Accepted	470ms	70108 KiB
		82	Accepted	240ms	75436 KiB
		83	Accepted	970ms	71264 KiB