oj.uz

Submission #975361

# Submission time Handle Problem Language Result Execution time Memory
975361 2024-05-05T03:11:08 Z happy_node Jail (JOI22_jail) C++17
100 / 100
 1281 ms 323092 KB 
#include <bits/stdc++.h>
using namespace std;

const int MX=1.2e5+5;
int Q,N,M;
int S[MX], T[MX];

vector<int> adj[MX], cyc[MX*40];

int up[MX][20], dep[MX], deg[MX*40];

int timer=0,tin[MX],tout[MX];

int valS[MX], valT[MX];

int idS[MX][20], idT[MX][20];

void dfs(int v, int p) {
	tin[v]=++timer;
	up[v][0]=p;
	for(int k=1;k<18;k++) {
		up[v][k]=up[up[v][k-1]][k-1];
	}
	for(auto u:adj[v]) {
		if(u==p) continue;
		dep[u]=dep[v]+1;
		dfs(u,v);
	}
	tout[v]=timer;
}

bool isAnc(int u, int v) { // u is the ancestor
	return tin[u]<=tin[v] && tout[v]<=tout[u];
}

int getLCA(int u, int v) {
	if(isAnc(u,v)) return u;
	if(isAnc(v,u)) return v;

	for(int k=17;k>=0;k--) {
		if(up[u][k]!=0 && !isAnc(up[u][k],v)) {
			u=up[u][k];
		}
	}
	return up[u][0];
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin>>Q;

	while(Q--) {
		cin>>N;

		for(int i=1;i<=N;i++) {
			valS[i]=-1;
			valT[i]=-1;
			dep[i]=0;
			adj[i].clear();

			for(int j=0;j<18;j++) {
				up[i][j]=0;
				idS[i][j]=0;
				idT[i][j]=0;
			}
		}

		for(int i=0;i<N-1;i++) {
			int u,v;
			cin>>u>>v;
			adj[u].push_back(v);
			adj[v].push_back(u);
		}

		tin[0]=0;
		tout[0]=1e9;

		timer=0;
		dfs(1,0);

		cin>>M;

		int id=M;
		for(int i=1;i<=N;i++) {
			for(int j=0;j<18;j++) {
				idS[i][j]=id++;
			}
		}
		for(int i=1;i<=N;i++) {
			for(int j=0;j<18;j++) {
				idT[i][j]=id++;
			}
		}
		for(int i=1;i<=N;i++) {
			for(int j=0;j<17;j++) {
				cyc[idS[i][j]].push_back(idS[i][j+1]);
				if(j>0 && up[i][j-1]!=0) cyc[idS[up[i][j-1]][j]].push_back(idS[i][j+1]);

				cyc[idT[i][j+1]].push_back(idT[i][j]);
				if(j>0 && up[i][j-1]!=0) cyc[idT[i][j+1]].push_back(idT[up[i][j-1]][j]);
			}
		}

		for(int i=0;i<M;i++) {
			cin>>S[i]>>T[i];

			valS[S[i]]=i;
			valT[T[i]]=i;
		}

		for(int i=0;i<M;i++) {
			int L=getLCA(S[i],T[i]);

			// everything within par(S[i]) to before L don't have tricky cases
			if(dep[S[i]]-dep[L]>=2) {
				int v=up[S[i]][0];
				for(int k=16;k>=0;k--) {
					if(up[v][k]!=0 && !isAnc(up[v][k],L)) {
						cyc[idS[v][k+1]].push_back(i);
						cyc[i].push_back(idT[v][k+1]);
						v=up[v][k];
					}
				}
				cyc[idS[v][0]].push_back(i);
				cyc[i].push_back(idT[v][0]);
			}
			if(dep[T[i]]-dep[L]>=2) {
				int v=up[T[i]][0];
				for(int k=16;k>=0;k--) {
					if(up[v][k]!=0 && !isAnc(up[v][k],L)) {
						cyc[idS[v][k+1]].push_back(i);
						cyc[i].push_back(idT[v][k+1]);
						v=up[v][k];
					}
				}
				cyc[idS[v][0]].push_back(i);
				cyc[i].push_back(idT[v][0]);
			}

			// connect to the base
			cyc[i].push_back(idS[S[i]][0]);
			cyc[idT[T[i]][0]].push_back(i);

			// this is for handling the cases on the edge to make sure 
			// we don't connect i with itself
			vector<int> cands={S[i],L,T[i]};
		
			for(auto x:cands) {
				// we just naively connect edges since there are <= 3 candidates
				if(valS[x]!=-1 && valS[x]!=i) 
					cyc[valS[x]].push_back(i);
				if(valT[x]!=-1 && valT[x]!=i) 
					cyc[i].push_back(valT[x]);
			}
		}

		for(int i=0;i<id;i++) {
			for(auto j:cyc[i]) {
				deg[j]+=1;
			}
		}

		queue<int> q;
		for(int i=0;i<id;i++) {
			if(!deg[i]) q.push(i);
		}

		int ans=0;
		while(!q.empty()) {
			auto v=q.front(); q.pop();
			ans+=1;
			for(auto u:cyc[v]) {
				deg[u]-=1;
				if(!deg[u]) q.push(u);
			}
		}

		cout<<(ans==id?"Yes":"No")<<'\n';

		for(int i=0;i<id;i++) {
			cyc[i].clear();
			deg[i]=0;
		}
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 117844 KB Output is correct
2 Correct 28 ms 117836 KB Output is correct
3 Correct 29 ms 117840 KB Output is correct
4 Correct 63 ms 118356 KB Output is correct
5 Correct 98 ms 118868 KB Output is correct
6 Correct 38 ms 118616 KB Output is correct
7 Correct 36 ms 118616 KB Output is correct
8 Correct 35 ms 118356 KB Output is correct
9 Correct 208 ms 128596 KB Output is correct
10 Correct 864 ms 305120 KB Output is correct
11 Correct 43 ms 118108 KB Output is correct
12 Correct 114 ms 119108 KB Output is correct
13 Correct 987 ms 309772 KB Output is correct
14 Correct 775 ms 309588 KB Output is correct
15 Correct 904 ms 311496 KB Output is correct
16 Correct 1281 ms 321792 KB Output is correct
17 Correct 1114 ms 312628 KB Output is correct
18 Correct 920 ms 314644 KB Output is correct
19 Correct 1075 ms 312496 KB Output is correct
20 Correct 977 ms 312660 KB Output is correct
21 Correct 801 ms 313192 KB Output is correct
22 Correct 752 ms 309840 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 117852 KB Output is correct
2 Correct 29 ms 117904 KB Output is correct
3 Correct 34 ms 118360 KB Output is correct
4 Correct 35 ms 118364 KB Output is correct
5 Correct 35 ms 118364 KB Output is correct
6 Correct 34 ms 118324 KB Output is correct
7 Correct 38 ms 118196 KB Output is correct
8 Correct 36 ms 118364 KB Output is correct
9 Correct 36 ms 118364 KB Output is correct
10 Correct 35 ms 118356 KB Output is correct
11 Correct 34 ms 118400 KB Output is correct
12 Correct 31 ms 118360 KB Output is correct
13 Correct 31 ms 118356 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 117852 KB Output is correct
2 Correct 29 ms 117904 KB Output is correct
3 Correct 34 ms 118360 KB Output is correct
4 Correct 35 ms 118364 KB Output is correct
5 Correct 35 ms 118364 KB Output is correct
6 Correct 34 ms 118324 KB Output is correct
7 Correct 38 ms 118196 KB Output is correct
8 Correct 36 ms 118364 KB Output is correct
9 Correct 36 ms 118364 KB Output is correct
10 Correct 35 ms 118356 KB Output is correct
11 Correct 34 ms 118400 KB Output is correct
12 Correct 31 ms 118360 KB Output is correct
13 Correct 31 ms 118356 KB Output is correct
14 Correct 33 ms 117844 KB Output is correct
15 Correct 29 ms 117948 KB Output is correct
16 Correct 33 ms 118352 KB Output is correct
17 Correct 34 ms 118364 KB Output is correct
18 Correct 33 ms 118356 KB Output is correct
19 Correct 29 ms 117852 KB Output is correct
20 Correct 34 ms 118364 KB Output is correct
21 Correct 36 ms 118360 KB Output is correct
22 Correct 34 ms 118364 KB Output is correct
23 Correct 30 ms 117852 KB Output is correct
24 Correct 29 ms 118108 KB Output is correct
25 Correct 34 ms 118364 KB Output is correct
26 Correct 32 ms 118364 KB Output is correct
27 Correct 35 ms 118360 KB Output is correct
28 Correct 30 ms 118016 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 117852 KB Output is correct
2 Correct 29 ms 117904 KB Output is correct
3 Correct 34 ms 118360 KB Output is correct
4 Correct 35 ms 118364 KB Output is correct
5 Correct 35 ms 118364 KB Output is correct
6 Correct 34 ms 118324 KB Output is correct
7 Correct 38 ms 118196 KB Output is correct
8 Correct 36 ms 118364 KB Output is correct
9 Correct 36 ms 118364 KB Output is correct
10 Correct 35 ms 118356 KB Output is correct
11 Correct 34 ms 118400 KB Output is correct
12 Correct 31 ms 118360 KB Output is correct
13 Correct 31 ms 118356 KB Output is correct
14 Correct 33 ms 117844 KB Output is correct
15 Correct 29 ms 117948 KB Output is correct
16 Correct 33 ms 118352 KB Output is correct
17 Correct 34 ms 118364 KB Output is correct
18 Correct 33 ms 118356 KB Output is correct
19 Correct 29 ms 117852 KB Output is correct
20 Correct 34 ms 118364 KB Output is correct
21 Correct 36 ms 118360 KB Output is correct
22 Correct 34 ms 118364 KB Output is correct
23 Correct 30 ms 117852 KB Output is correct
24 Correct 29 ms 118108 KB Output is correct
25 Correct 34 ms 118364 KB Output is correct
26 Correct 32 ms 118364 KB Output is correct
27 Correct 35 ms 118360 KB Output is correct
28 Correct 30 ms 118016 KB Output is correct
29 Correct 34 ms 118260 KB Output is correct
30 Correct 35 ms 118360 KB Output is correct
31 Correct 35 ms 118464 KB Output is correct
32 Correct 35 ms 118444 KB Output is correct
33 Correct 35 ms 118368 KB Output is correct
34 Correct 33 ms 118556 KB Output is correct
35 Correct 33 ms 118096 KB Output is correct
36 Correct 33 ms 118352 KB Output is correct
37 Correct 34 ms 118356 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 117852 KB Output is correct
2 Correct 29 ms 117904 KB Output is correct
3 Correct 34 ms 118360 KB Output is correct
4 Correct 35 ms 118364 KB Output is correct
5 Correct 35 ms 118364 KB Output is correct
6 Correct 34 ms 118324 KB Output is correct
7 Correct 38 ms 118196 KB Output is correct
8 Correct 36 ms 118364 KB Output is correct
9 Correct 36 ms 118364 KB Output is correct
10 Correct 35 ms 118356 KB Output is correct
11 Correct 34 ms 118400 KB Output is correct
12 Correct 31 ms 118360 KB Output is correct
13 Correct 31 ms 118356 KB Output is correct
14 Correct 33 ms 117844 KB Output is correct
15 Correct 29 ms 117948 KB Output is correct
16 Correct 33 ms 118352 KB Output is correct
17 Correct 34 ms 118364 KB Output is correct
18 Correct 33 ms 118356 KB Output is correct
19 Correct 29 ms 117852 KB Output is correct
20 Correct 34 ms 118364 KB Output is correct
21 Correct 36 ms 118360 KB Output is correct
22 Correct 34 ms 118364 KB Output is correct
23 Correct 30 ms 117852 KB Output is correct
24 Correct 29 ms 118108 KB Output is correct
25 Correct 34 ms 118364 KB Output is correct
26 Correct 32 ms 118364 KB Output is correct
27 Correct 35 ms 118360 KB Output is correct
28 Correct 30 ms 118016 KB Output is correct
29 Correct 34 ms 118260 KB Output is correct
30 Correct 35 ms 118360 KB Output is correct
31 Correct 35 ms 118464 KB Output is correct
32 Correct 35 ms 118444 KB Output is correct
33 Correct 35 ms 118368 KB Output is correct
34 Correct 33 ms 118556 KB Output is correct
35 Correct 33 ms 118096 KB Output is correct
36 Correct 33 ms 118352 KB Output is correct
37 Correct 34 ms 118356 KB Output is correct
38 Correct 261 ms 128836 KB Output is correct
39 Correct 868 ms 304724 KB Output is correct
40 Correct 220 ms 129668 KB Output is correct
41 Correct 217 ms 128556 KB Output is correct
42 Correct 177 ms 129216 KB Output is correct
43 Correct 263 ms 129680 KB Output is correct
44 Correct 52 ms 119728 KB Output is correct
45 Correct 738 ms 299680 KB Output is correct
46 Correct 713 ms 299600 KB Output is correct
47 Correct 892 ms 301608 KB Output is correct
48 Correct 933 ms 301352 KB Output is correct
49 Correct 702 ms 302180 KB Output is correct
50 Correct 742 ms 302356 KB Output is correct
51 Correct 762 ms 303444 KB Output is correct
52 Correct 805 ms 303224 KB Output is correct
53 Correct 83 ms 131016 KB Output is correct
54 Correct 928 ms 299668 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 117852 KB Output is correct
2 Correct 29 ms 117852 KB Output is correct
3 Correct 30 ms 117844 KB Output is correct
4 Correct 33 ms 117840 KB Output is correct
5 Correct 47 ms 118096 KB Output is correct
6 Correct 32 ms 118364 KB Output is correct
7 Correct 32 ms 118360 KB Output is correct
8 Correct 29 ms 117848 KB Output is correct
9 Correct 29 ms 117844 KB Output is correct
10 Correct 29 ms 118356 KB Output is correct
11 Correct 30 ms 117852 KB Output is correct
12 Correct 33 ms 118364 KB Output is correct
13 Correct 76 ms 118724 KB Output is correct
14 Correct 128 ms 119112 KB Output is correct
15 Correct 114 ms 118924 KB Output is correct
16 Correct 879 ms 300452 KB Output is correct
17 Correct 806 ms 307512 KB Output is correct
18 Correct 1006 ms 317832 KB Output is correct
19 Correct 843 ms 302512 KB Output is correct
20 Correct 865 ms 301620 KB Output is correct
21 Correct 843 ms 301656 KB Output is correct
22 Correct 834 ms 306876 KB Output is correct
23 Correct 720 ms 306476 KB Output is correct
24 Correct 904 ms 307020 KB Output is correct
25 Correct 870 ms 307164 KB Output is correct
26 Correct 889 ms 306992 KB Output is correct
27 Correct 646 ms 308424 KB Output is correct
28 Correct 530 ms 308444 KB Output is correct
29 Correct 547 ms 308880 KB Output is correct
30 Correct 729 ms 303056 KB Output is correct
31 Correct 675 ms 303412 KB Output is correct
32 Correct 755 ms 303368 KB Output is correct
33 Correct 638 ms 303380 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 117844 KB Output is correct
2 Correct 28 ms 117836 KB Output is correct
3 Correct 29 ms 117840 KB Output is correct
4 Correct 63 ms 118356 KB Output is correct
5 Correct 98 ms 118868 KB Output is correct
6 Correct 38 ms 118616 KB Output is correct
7 Correct 36 ms 118616 KB Output is correct
8 Correct 35 ms 118356 KB Output is correct
9 Correct 208 ms 128596 KB Output is correct
10 Correct 864 ms 305120 KB Output is correct
11 Correct 43 ms 118108 KB Output is correct
12 Correct 114 ms 119108 KB Output is correct
13 Correct 987 ms 309772 KB Output is correct
14 Correct 775 ms 309588 KB Output is correct
15 Correct 904 ms 311496 KB Output is correct
16 Correct 1281 ms 321792 KB Output is correct
17 Correct 1114 ms 312628 KB Output is correct
18 Correct 920 ms 314644 KB Output is correct
19 Correct 1075 ms 312496 KB Output is correct
20 Correct 977 ms 312660 KB Output is correct
21 Correct 801 ms 313192 KB Output is correct
22 Correct 752 ms 309840 KB Output is correct
23 Correct 30 ms 117852 KB Output is correct
24 Correct 29 ms 117904 KB Output is correct
25 Correct 34 ms 118360 KB Output is correct
26 Correct 35 ms 118364 KB Output is correct
27 Correct 35 ms 118364 KB Output is correct
28 Correct 34 ms 118324 KB Output is correct
29 Correct 38 ms 118196 KB Output is correct
30 Correct 36 ms 118364 KB Output is correct
31 Correct 36 ms 118364 KB Output is correct
32 Correct 35 ms 118356 KB Output is correct
33 Correct 34 ms 118400 KB Output is correct
34 Correct 31 ms 118360 KB Output is correct
35 Correct 31 ms 118356 KB Output is correct
36 Correct 33 ms 117844 KB Output is correct
37 Correct 29 ms 117948 KB Output is correct
38 Correct 33 ms 118352 KB Output is correct
39 Correct 34 ms 118364 KB Output is correct
40 Correct 33 ms 118356 KB Output is correct
41 Correct 29 ms 117852 KB Output is correct
42 Correct 34 ms 118364 KB Output is correct
43 Correct 36 ms 118360 KB Output is correct
44 Correct 34 ms 118364 KB Output is correct
45 Correct 30 ms 117852 KB Output is correct
46 Correct 29 ms 118108 KB Output is correct
47 Correct 34 ms 118364 KB Output is correct
48 Correct 32 ms 118364 KB Output is correct
49 Correct 35 ms 118360 KB Output is correct
50 Correct 30 ms 118016 KB Output is correct
51 Correct 34 ms 118260 KB Output is correct
52 Correct 35 ms 118360 KB Output is correct
53 Correct 35 ms 118464 KB Output is correct
54 Correct 35 ms 118444 KB Output is correct
55 Correct 35 ms 118368 KB Output is correct
56 Correct 33 ms 118556 KB Output is correct
57 Correct 33 ms 118096 KB Output is correct
58 Correct 33 ms 118352 KB Output is correct
59 Correct 34 ms 118356 KB Output is correct
60 Correct 261 ms 128836 KB Output is correct
61 Correct 868 ms 304724 KB Output is correct
62 Correct 220 ms 129668 KB Output is correct
63 Correct 217 ms 128556 KB Output is correct
64 Correct 177 ms 129216 KB Output is correct
65 Correct 263 ms 129680 KB Output is correct
66 Correct 52 ms 119728 KB Output is correct
67 Correct 738 ms 299680 KB Output is correct
68 Correct 713 ms 299600 KB Output is correct
69 Correct 892 ms 301608 KB Output is correct
70 Correct 933 ms 301352 KB Output is correct
71 Correct 702 ms 302180 KB Output is correct
72 Correct 742 ms 302356 KB Output is correct
73 Correct 762 ms 303444 KB Output is correct
74 Correct 805 ms 303224 KB Output is correct
75 Correct 83 ms 131016 KB Output is correct
76 Correct 928 ms 299668 KB Output is correct
77 Correct 29 ms 117852 KB Output is correct
78 Correct 29 ms 117852 KB Output is correct
79 Correct 30 ms 117844 KB Output is correct
80 Correct 33 ms 117840 KB Output is correct
81 Correct 47 ms 118096 KB Output is correct
82 Correct 32 ms 118364 KB Output is correct
83 Correct 32 ms 118360 KB Output is correct
84 Correct 29 ms 117848 KB Output is correct
85 Correct 29 ms 117844 KB Output is correct
86 Correct 29 ms 118356 KB Output is correct
87 Correct 30 ms 117852 KB Output is correct
88 Correct 33 ms 118364 KB Output is correct
89 Correct 76 ms 118724 KB Output is correct
90 Correct 128 ms 119112 KB Output is correct
91 Correct 114 ms 118924 KB Output is correct
92 Correct 879 ms 300452 KB Output is correct
93 Correct 806 ms 307512 KB Output is correct
94 Correct 1006 ms 317832 KB Output is correct
95 Correct 843 ms 302512 KB Output is correct
96 Correct 865 ms 301620 KB Output is correct
97 Correct 843 ms 301656 KB Output is correct
98 Correct 834 ms 306876 KB Output is correct
99 Correct 720 ms 306476 KB Output is correct
100 Correct 904 ms 307020 KB Output is correct
101 Correct 870 ms 307164 KB Output is correct
102 Correct 889 ms 306992 KB Output is correct
103 Correct 646 ms 308424 KB Output is correct
104 Correct 530 ms 308444 KB Output is correct
105 Correct 547 ms 308880 KB Output is correct
106 Correct 729 ms 303056 KB Output is correct
107 Correct 675 ms 303412 KB Output is correct
108 Correct 755 ms 303368 KB Output is correct
109 Correct 638 ms 303380 KB Output is correct
110 Correct 126 ms 119236 KB Output is correct
111 Correct 98 ms 118864 KB Output is correct
112 Correct 972 ms 312440 KB Output is correct
113 Correct 1075 ms 304900 KB Output is correct
114 Correct 850 ms 309532 KB Output is correct
115 Correct 451 ms 298260 KB Output is correct
116 Correct 918 ms 305036 KB Output is correct
117 Correct 1127 ms 319760 KB Output is correct
118 Correct 962 ms 299992 KB Output is correct
119 Correct 898 ms 299948 KB Output is correct
120 Correct 80 ms 133564 KB Output is correct
121 Correct 1055 ms 306448 KB Output is correct
122 Correct 1056 ms 306208 KB Output is correct
123 Correct 1135 ms 305748 KB Output is correct
124 Correct 868 ms 305620 KB Output is correct
125 Correct 1062 ms 306084 KB Output is correct
126 Correct 1237 ms 323092 KB Output is correct
127 Correct 1091 ms 314776 KB Output is correct
128 Correct 972 ms 314696 KB Output is correct
129 Correct 1162 ms 314980 KB Output is correct
130 Correct 992 ms 314720 KB Output is correct