oj.uz

Submission #635248

# Submission time Handle Problem Language Result Execution time Memory
635248 2022-08-25T17:54:10 Z alvingogo Jail (JOI22_jail) C++14
100 / 100
 1519 ms 315076 KB 
#include <bits/stdc++.h>
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define cd complex<double>
#define p_q priority_queue
using namespace std;

struct TOPO{
	vector<vector<int> > e;
	int n;
	vector<int> in;
	void init(int x){
		e.resize(x);
		in.resize(x);
		n=x;
	}
	void add(int x,int y){
		if(x<0 || y<0){
			return;
		}
		//cout << x << " " << y << "\n";
		e[x].push_back(y);
		in[y]++;
	}
	bool solve(){
		int cnt=0;
		queue<int> q;
		for(int i=0;i<n;i++){
			if(in[i]==0){
				q.push(i);
			}
		}
		while(q.size()){
			int a=q.front();
			q.pop();
			cnt++;
			for(auto h:e[a]){
				in[h]--;
				if(in[h]==0){
					q.push(h);
				}
			}
		}
		return cnt==n;
	}
};
const int all=18;
struct no{
	vector<int> ch;
	int dep=-1;
	int fa=-1;
	int as[all]={0};
};
vector<no> v;
void dfs(int r,int f){
	v[r].dep=v[f].dep+1;
	v[r].as[0]=f;
	for(auto h:v[r].ch){
		if(h!=f){
			dfs(h,r);
		}
	}
}
int main(){
	AquA;
	int q;
	cin >> q;
	while(q--){
		int n;
		cin >> n;
		v.clear();
		v.resize(n);
		for(int i=1;i<n;i++){
			int a,b;
			cin >> a >> b;
			a--;
			b--;
			v[a].ch.push_back(b);
			v[b].ch.push_back(a);
		}
		dfs(0,0);
		int m;
		cin >> m;
		vector<pair<int,int> > g;
		vector<int> s(n,-1),t(n,-1);
		TOPO tp;
		tp.init(m+2*all*n+2*n);
		for(int i=0;i<m;i++){
			int a,b;
			cin >> a >> b;
			a--;
			b--;
			s[a]=i;
			tp.add(i,m+all*2*n+a);
			t[b]=i;
			tp.add(m+all*2*n+n+b,i);
			g.push_back({a,b});
		}
		for(int i=0;i<n;i++){
			tp.add(m+all*2*n+i,m+all*i);
			tp.add(m+all*2*n+v[i].as[0],m+all*i);
			tp.add(m+all*n+all*i,m+all*2*n+n+i);
			tp.add(m+all*n+all*i,m+all*2*n+n+v[i].as[0]);
		}
		for(int i=1;i<all;i++){
			for(int j=0;j<n;j++){
				v[j].as[i]=v[v[j].as[i-1]].as[i-1];
				tp.add(m+all*j+i-1,m+all*j+i);
				tp.add(m+all*v[j].as[i-1]+i-1,m+all*j+i);
				tp.add(m+all*n+all*j+i,m+all*n+all*j+i-1);
				tp.add(m+all*n+all*j+i,m+all*n+all*v[j].as[i-1]+i-1);
			}
		}
		auto query=[&](int r,int f,int cnt){
			if(r==f){
				return;
			}
			for(int i=all-1;i>=0;i--){
				if(v[v[r].as[i]].dep>v[f].dep){
					tp.add(m+all*r+i,cnt);
					tp.add(cnt,m+all*n+all*r+i);
					r=v[r].as[i];
				}
			}
			tp.add(m+all*2*n+r,cnt);
			tp.add(cnt,m+all*2*n+n+r);
		};
		int cnt=0;
		for(auto h:g){
			int a=h.fs,b=h.sc;
			int lca;
			if(v[a].dep>v[b].dep){
				for(int i=all-1;i>=0;i--){
					if(v[v[a].as[i]].dep>=v[b].dep){
						a=v[a].as[i];
					}
				}
			}
			else if(v[b].dep>v[a].dep){
				for(int i=all-1;i>=0;i--){
					if(v[v[b].as[i]].dep>=v[a].dep){
						b=v[b].as[i];
					}
				}
			}
			if(a==b){
				lca=a;
			}
			else{
				for(int i=all-1;i>=0;i--){
					if(v[b].as[i]!=v[a].as[i]){
						a=v[a].as[i];
						b=v[b].as[i];
					}
				}
				lca=v[a].as[0];
			}
			a=h.fs;
			b=h.sc;
			tp.add(cnt,t[a]);
			tp.add(s[b],cnt);
			if(lca==a){
				b=v[b].as[0];
				query(b,a,cnt);
			}
			else if(lca==b){
				a=v[a].as[0];
				query(a,b,cnt);
			}
			else{
				a=v[a].as[0];
				b=v[b].as[0];
				query(a,lca,cnt);
				query(b,lca,cnt);
				tp.add(cnt,t[lca]);
				tp.add(s[lca],cnt);
			}
			cnt++;
		}
		if(tp.solve()){
			cout << "Yes\n";
		}
		else{
			cout << "No\n";
		}
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 202 ms 596 KB Output is correct
5 Correct 432 ms 596 KB Output is correct
6 Correct 24 ms 928 KB Output is correct
7 Correct 19 ms 932 KB Output is correct
8 Correct 21 ms 880 KB Output is correct
9 Correct 571 ms 14776 KB Output is correct
10 Correct 904 ms 284640 KB Output is correct
11 Correct 83 ms 368 KB Output is correct
12 Correct 446 ms 1680 KB Output is correct
13 Correct 1097 ms 293572 KB Output is correct
14 Correct 782 ms 293580 KB Output is correct
15 Correct 889 ms 295060 KB Output is correct
16 Correct 1183 ms 309628 KB Output is correct
17 Correct 1041 ms 297104 KB Output is correct
18 Correct 1096 ms 298716 KB Output is correct
19 Correct 1040 ms 297068 KB Output is correct
20 Correct 892 ms 297132 KB Output is correct
21 Correct 699 ms 296756 KB Output is correct
22 Correct 752 ms 292368 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 20 ms 928 KB Output is correct
4 Correct 20 ms 928 KB Output is correct
5 Correct 20 ms 884 KB Output is correct
6 Correct 19 ms 928 KB Output is correct
7 Correct 20 ms 932 KB Output is correct
8 Correct 21 ms 884 KB Output is correct
9 Correct 20 ms 924 KB Output is correct
10 Correct 19 ms 928 KB Output is correct
11 Correct 16 ms 928 KB Output is correct
12 Correct 9 ms 932 KB Output is correct
13 Correct 9 ms 928 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 20 ms 928 KB Output is correct
4 Correct 20 ms 928 KB Output is correct
5 Correct 20 ms 884 KB Output is correct
6 Correct 19 ms 928 KB Output is correct
7 Correct 20 ms 932 KB Output is correct
8 Correct 21 ms 884 KB Output is correct
9 Correct 20 ms 924 KB Output is correct
10 Correct 19 ms 928 KB Output is correct
11 Correct 16 ms 928 KB Output is correct
12 Correct 9 ms 932 KB Output is correct
13 Correct 9 ms 928 KB Output is correct
14 Correct 1 ms 316 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 19 ms 972 KB Output is correct
17 Correct 23 ms 872 KB Output is correct
18 Correct 23 ms 968 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 21 ms 872 KB Output is correct
21 Correct 20 ms 964 KB Output is correct
22 Correct 19 ms 968 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 20 ms 1108 KB Output is correct
26 Correct 4 ms 884 KB Output is correct
27 Correct 21 ms 936 KB Output is correct
28 Correct 3 ms 340 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 20 ms 928 KB Output is correct
4 Correct 20 ms 928 KB Output is correct
5 Correct 20 ms 884 KB Output is correct
6 Correct 19 ms 928 KB Output is correct
7 Correct 20 ms 932 KB Output is correct
8 Correct 21 ms 884 KB Output is correct
9 Correct 20 ms 924 KB Output is correct
10 Correct 19 ms 928 KB Output is correct
11 Correct 16 ms 928 KB Output is correct
12 Correct 9 ms 932 KB Output is correct
13 Correct 9 ms 928 KB Output is correct
14 Correct 1 ms 316 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 19 ms 972 KB Output is correct
17 Correct 23 ms 872 KB Output is correct
18 Correct 23 ms 968 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 21 ms 872 KB Output is correct
21 Correct 20 ms 964 KB Output is correct
22 Correct 19 ms 968 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 20 ms 1108 KB Output is correct
26 Correct 4 ms 884 KB Output is correct
27 Correct 21 ms 936 KB Output is correct
28 Correct 3 ms 340 KB Output is correct
29 Correct 21 ms 980 KB Output is correct
30 Correct 24 ms 1168 KB Output is correct
31 Correct 19 ms 1008 KB Output is correct
32 Correct 21 ms 884 KB Output is correct
33 Correct 19 ms 884 KB Output is correct
34 Correct 16 ms 880 KB Output is correct
35 Correct 19 ms 852 KB Output is correct
36 Correct 14 ms 860 KB Output is correct
37 Correct 12 ms 852 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 20 ms 928 KB Output is correct
4 Correct 20 ms 928 KB Output is correct
5 Correct 20 ms 884 KB Output is correct
6 Correct 19 ms 928 KB Output is correct
7 Correct 20 ms 932 KB Output is correct
8 Correct 21 ms 884 KB Output is correct
9 Correct 20 ms 924 KB Output is correct
10 Correct 19 ms 928 KB Output is correct
11 Correct 16 ms 928 KB Output is correct
12 Correct 9 ms 932 KB Output is correct
13 Correct 9 ms 928 KB Output is correct
14 Correct 1 ms 316 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 19 ms 972 KB Output is correct
17 Correct 23 ms 872 KB Output is correct
18 Correct 23 ms 968 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 21 ms 872 KB Output is correct
21 Correct 20 ms 964 KB Output is correct
22 Correct 19 ms 968 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 20 ms 1108 KB Output is correct
26 Correct 4 ms 884 KB Output is correct
27 Correct 21 ms 936 KB Output is correct
28 Correct 3 ms 340 KB Output is correct
29 Correct 21 ms 980 KB Output is correct
30 Correct 24 ms 1168 KB Output is correct
31 Correct 19 ms 1008 KB Output is correct
32 Correct 21 ms 884 KB Output is correct
33 Correct 19 ms 884 KB Output is correct
34 Correct 16 ms 880 KB Output is correct
35 Correct 19 ms 852 KB Output is correct
36 Correct 14 ms 860 KB Output is correct
37 Correct 12 ms 852 KB Output is correct
38 Correct 581 ms 15900 KB Output is correct
39 Correct 834 ms 286176 KB Output is correct
40 Correct 641 ms 16068 KB Output is correct
41 Correct 629 ms 15972 KB Output is correct
42 Correct 589 ms 16108 KB Output is correct
43 Correct 706 ms 15748 KB Output is correct
44 Correct 87 ms 3004 KB Output is correct
45 Correct 772 ms 287316 KB Output is correct
46 Correct 812 ms 287416 KB Output is correct
47 Correct 953 ms 283968 KB Output is correct
48 Correct 968 ms 283968 KB Output is correct
49 Correct 803 ms 287956 KB Output is correct
50 Correct 879 ms 287944 KB Output is correct
51 Correct 916 ms 287216 KB Output is correct
52 Correct 961 ms 287160 KB Output is correct
53 Correct 148 ms 20132 KB Output is correct
54 Correct 1174 ms 288052 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 89 ms 372 KB Output is correct
6 Correct 9 ms 876 KB Output is correct
7 Correct 11 ms 880 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 15 ms 864 KB Output is correct
13 Correct 279 ms 1108 KB Output is correct
14 Correct 475 ms 1488 KB Output is correct
15 Correct 359 ms 1316 KB Output is correct
16 Correct 978 ms 289988 KB Output is correct
17 Correct 942 ms 299936 KB Output is correct
18 Correct 1055 ms 314116 KB Output is correct
19 Correct 965 ms 292340 KB Output is correct
20 Correct 979 ms 291628 KB Output is correct
21 Correct 1020 ms 291792 KB Output is correct
22 Correct 1018 ms 299508 KB Output is correct
23 Correct 806 ms 299304 KB Output is correct
24 Correct 1268 ms 299264 KB Output is correct
25 Correct 1199 ms 299760 KB Output is correct
26 Correct 1247 ms 299540 KB Output is correct
27 Correct 879 ms 301588 KB Output is correct
28 Correct 743 ms 301596 KB Output is correct
29 Correct 717 ms 301416 KB Output is correct
30 Correct 1091 ms 294456 KB Output is correct
31 Correct 927 ms 294680 KB Output is correct
32 Correct 1177 ms 294564 KB Output is correct
33 Correct 910 ms 294576 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 202 ms 596 KB Output is correct
5 Correct 432 ms 596 KB Output is correct
6 Correct 24 ms 928 KB Output is correct
7 Correct 19 ms 932 KB Output is correct
8 Correct 21 ms 880 KB Output is correct
9 Correct 571 ms 14776 KB Output is correct
10 Correct 904 ms 284640 KB Output is correct
11 Correct 83 ms 368 KB Output is correct
12 Correct 446 ms 1680 KB Output is correct
13 Correct 1097 ms 293572 KB Output is correct
14 Correct 782 ms 293580 KB Output is correct
15 Correct 889 ms 295060 KB Output is correct
16 Correct 1183 ms 309628 KB Output is correct
17 Correct 1041 ms 297104 KB Output is correct
18 Correct 1096 ms 298716 KB Output is correct
19 Correct 1040 ms 297068 KB Output is correct
20 Correct 892 ms 297132 KB Output is correct
21 Correct 699 ms 296756 KB Output is correct
22 Correct 752 ms 292368 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 20 ms 928 KB Output is correct
26 Correct 20 ms 928 KB Output is correct
27 Correct 20 ms 884 KB Output is correct
28 Correct 19 ms 928 KB Output is correct
29 Correct 20 ms 932 KB Output is correct
30 Correct 21 ms 884 KB Output is correct
31 Correct 20 ms 924 KB Output is correct
32 Correct 19 ms 928 KB Output is correct
33 Correct 16 ms 928 KB Output is correct
34 Correct 9 ms 932 KB Output is correct
35 Correct 9 ms 928 KB Output is correct
36 Correct 1 ms 316 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 19 ms 972 KB Output is correct
39 Correct 23 ms 872 KB Output is correct
40 Correct 23 ms 968 KB Output is correct
41 Correct 3 ms 340 KB Output is correct
42 Correct 21 ms 872 KB Output is correct
43 Correct 20 ms 964 KB Output is correct
44 Correct 19 ms 968 KB Output is correct
45 Correct 2 ms 340 KB Output is correct
46 Correct 2 ms 596 KB Output is correct
47 Correct 20 ms 1108 KB Output is correct
48 Correct 4 ms 884 KB Output is correct
49 Correct 21 ms 936 KB Output is correct
50 Correct 3 ms 340 KB Output is correct
51 Correct 21 ms 980 KB Output is correct
52 Correct 24 ms 1168 KB Output is correct
53 Correct 19 ms 1008 KB Output is correct
54 Correct 21 ms 884 KB Output is correct
55 Correct 19 ms 884 KB Output is correct
56 Correct 16 ms 880 KB Output is correct
57 Correct 19 ms 852 KB Output is correct
58 Correct 14 ms 860 KB Output is correct
59 Correct 12 ms 852 KB Output is correct
60 Correct 581 ms 15900 KB Output is correct
61 Correct 834 ms 286176 KB Output is correct
62 Correct 641 ms 16068 KB Output is correct
63 Correct 629 ms 15972 KB Output is correct
64 Correct 589 ms 16108 KB Output is correct
65 Correct 706 ms 15748 KB Output is correct
66 Correct 87 ms 3004 KB Output is correct
67 Correct 772 ms 287316 KB Output is correct
68 Correct 812 ms 287416 KB Output is correct
69 Correct 953 ms 283968 KB Output is correct
70 Correct 968 ms 283968 KB Output is correct
71 Correct 803 ms 287956 KB Output is correct
72 Correct 879 ms 287944 KB Output is correct
73 Correct 916 ms 287216 KB Output is correct
74 Correct 961 ms 287160 KB Output is correct
75 Correct 148 ms 20132 KB Output is correct
76 Correct 1174 ms 288052 KB Output is correct
77 Correct 1 ms 212 KB Output is correct
78 Correct 0 ms 212 KB Output is correct
79 Correct 1 ms 340 KB Output is correct
80 Correct 1 ms 212 KB Output is correct
81 Correct 89 ms 372 KB Output is correct
82 Correct 9 ms 876 KB Output is correct
83 Correct 11 ms 880 KB Output is correct
84 Correct 2 ms 340 KB Output is correct
85 Correct 2 ms 340 KB Output is correct
86 Correct 2 ms 596 KB Output is correct
87 Correct 3 ms 340 KB Output is correct
88 Correct 15 ms 864 KB Output is correct
89 Correct 279 ms 1108 KB Output is correct
90 Correct 475 ms 1488 KB Output is correct
91 Correct 359 ms 1316 KB Output is correct
92 Correct 978 ms 289988 KB Output is correct
93 Correct 942 ms 299936 KB Output is correct
94 Correct 1055 ms 314116 KB Output is correct
95 Correct 965 ms 292340 KB Output is correct
96 Correct 979 ms 291628 KB Output is correct
97 Correct 1020 ms 291792 KB Output is correct
98 Correct 1018 ms 299508 KB Output is correct
99 Correct 806 ms 299304 KB Output is correct
100 Correct 1268 ms 299264 KB Output is correct
101 Correct 1199 ms 299760 KB Output is correct
102 Correct 1247 ms 299540 KB Output is correct
103 Correct 879 ms 301588 KB Output is correct
104 Correct 743 ms 301596 KB Output is correct
105 Correct 717 ms 301416 KB Output is correct
106 Correct 1091 ms 294456 KB Output is correct
107 Correct 927 ms 294680 KB Output is correct
108 Correct 1177 ms 294564 KB Output is correct
109 Correct 910 ms 294576 KB Output is correct
110 Correct 486 ms 1952 KB Output is correct
111 Correct 428 ms 1216 KB Output is correct
112 Correct 1076 ms 300744 KB Output is correct
113 Correct 1233 ms 289100 KB Output is correct
114 Correct 876 ms 298764 KB Output is correct
115 Correct 710 ms 288908 KB Output is correct
116 Correct 1252 ms 295308 KB Output is correct
117 Correct 1209 ms 315076 KB Output is correct
118 Correct 1204 ms 288196 KB Output is correct
119 Correct 1199 ms 288256 KB Output is correct
120 Correct 84 ms 25076 KB Output is correct
121 Correct 1519 ms 297756 KB Output is correct
122 Correct 1517 ms 297784 KB Output is correct
123 Correct 1307 ms 289324 KB Output is correct
124 Correct 896 ms 289384 KB Output is correct
125 Correct 1266 ms 289924 KB Output is correct
126 Correct 1343 ms 314220 KB Output is correct
127 Correct 1116 ms 302208 KB Output is correct
128 Correct 994 ms 302004 KB Output is correct
129 Correct 1289 ms 302276 KB Output is correct
130 Correct 1064 ms 302404 KB Output is correct