Submission #4,668

2023-03-30 18:53:36

cpp17

Wrong answer 45/100

1.511s

43488 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[path[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[path[que[i].l]]];
            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	19ms	11076 KiB
subtask2	5/5
		2	Accepted	20ms	11292 KiB
		3	Accepted	20ms	11788 KiB
		4	Accepted	19ms	11880 KiB
		5	Accepted	20ms	12100 KiB
		6	Accepted	20ms	12556 KiB
		7	Accepted	20ms	12660 KiB
		8	Accepted	21ms	12636 KiB
		9	Accepted	20ms	12800 KiB
		10	Accepted	20ms	13004 KiB
		11	Accepted	20ms	13272 KiB
subtask3	0/5
		12	Accepted	19ms	13304 KiB
		13	Accepted	19ms	13252 KiB
		14	Wrong answer	20ms	13480 KiB
		15	Accepted	20ms	13468 KiB
		16	Accepted	20ms	13352 KiB
		17	Accepted	21ms	13436 KiB
		18	Accepted	21ms	13488 KiB
		19	Accepted	21ms	13660 KiB
		20	Wrong answer	21ms	13572 KiB
		21	Wrong answer	21ms	13572 KiB
subtask4	10/10
		22	Accepted	35ms	15416 KiB
		23	Accepted	133ms	19804 KiB
		24	Accepted	207ms	28396 KiB
		25	Accepted	296ms	35404 KiB
		26	Accepted	340ms	39820 KiB
		27	Accepted	342ms	39464 KiB
subtask5	0/10
		28	Wrong answer	48ms	15296 KiB
		29	Wrong answer	158ms	19236 KiB
		30	Wrong answer	566ms	26484 KiB
		31	Wrong answer	1.195s	31896 KiB
		32	Wrong answer	1.511s	33976 KiB
		33	Wrong answer	1.511s	34032 KiB
subtask6	10/10
		34	Accepted	21ms	14216 KiB
		35	Accepted	32ms	16188 KiB
		36	Accepted	81ms	21132 KiB
		37	Accepted	164ms	29924 KiB
		38	Accepted	238ms	38196 KiB
		39	Accepted	263ms	39052 KiB
		40	Accepted	263ms	42452 KiB
		41	Accepted	280ms	39496 KiB
subtask7	0/15
		42	Accepted	21ms	14384 KiB
		43	Accepted	37ms	15768 KiB
		44	Accepted	97ms	19724 KiB
		45	Accepted	254ms	26904 KiB
		46	Accepted	465ms	32512 KiB
		47	Accepted	555ms	34440 KiB
		48	Accepted	551ms	34404 KiB
		49	Accepted	545ms	34316 KiB
		50	Wrong answer	597ms	34284 KiB
		51	Wrong answer	130ms	37972 KiB
		52	Accepted	165ms	30660 KiB
		53	Accepted	164ms	36464 KiB
		54	Wrong answer	131ms	37964 KiB
		55	Accepted	168ms	30596 KiB
		56	Accepted	1.113s	30548 KiB
subtask8	20/20
		57	Accepted	35ms	16116 KiB
		58	Accepted	76ms	21084 KiB
		59	Accepted	158ms	25664 KiB
		60	Accepted	263ms	31484 KiB
		61	Accepted	272ms	40692 KiB
		62	Accepted	273ms	42912 KiB
		63	Accepted	397ms	39664 KiB
		64	Accepted	342ms	40228 KiB
		65	Accepted	179ms	43488 KiB
		66	Accepted	175ms	43452 KiB
subtask9	0/25
		67	Wrong answer	43ms	15804 KiB
		68	Accepted	90ms	19348 KiB
		69	Wrong answer	194ms	23448 KiB
		70	Wrong answer	624ms	27284 KiB
		71	Accepted	529ms	34244 KiB
		72	Accepted	546ms	34424 KiB
		73	Wrong answer	1.166s	34412 KiB
		74	Wrong answer	822ms	34416 KiB
		75	Wrong answer	675ms	34380 KiB
		76	Wrong answer	837ms	34376 KiB
		77	Wrong answer	906ms	34428 KiB
		78	Wrong answer	749ms	34388 KiB
		79	Wrong answer	925ms	34412 KiB
		80	Accepted	374ms	38024 KiB
		81	Accepted	404ms	38040 KiB
		82	Accepted	175ms	43356 KiB
		83	Accepted	852ms	39188 KiB