Submission #1102772

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1102772	2024-10-18T20:22:36 Z	Bula	Jail (JOI22_jail)	C++17	0 / 100	18 ms	596 KB

jail

#include <bits/stdc++.h>
using namespace std;

main(){
	int tt = 1; cin >> tt;
	while(tt--){
		int n;
		cin >> n;
		vector<int> adj[n + 1];
		for(int i = 1; i <= n - 1; i++){
			int x, y;
			cin >> x >> y;
			adj[x].push_back(y);
			adj[y].push_back(x);
		}
		vector<int> par(n + 1), d(n + 1);
		function<void(int, int)> dfs = [&](int v, int p){
			par[v] = p; d[v] = d[p] + 1;
			for(auto x : adj[v]){
				if(x == p) continue;
				dfs(x, v);
			}
		};
		dfs(1, 0);
		int q;
		cin >> q;
		vector<int> a(q + 1), b(q + 1), g[n + 1], s[n + 1];
		for(int i = 1; i <= q; i++){
			cin >> a[i] >> b[i];
			g[b[i]].push_back(i);
			s[a[i]].push_back(i);
		}
		int ok = 1;
		vector<int> G[q + 1], in(q + 1);
		for(int i = 1; i <= q; i++){
			vector<int> m(q + 1);
			int x = a[i], y = par[b[i]];
			while(x != y){
				if(d[x] < d[y]) swap(x, y);
				for(auto u : g[x]){
					if(u == i) continue;
					G[i].push_back(u);
					in[u]++;
					m[u]++;
					if(m[u] == 2) ok = 0;
				}
				for(auto u : s[x]){
					m[u]++;
					if(m[u] == 2) ok = 0;
				}
				x = par[x];
			}
		}
		queue<int> Q;
		for(int i = 1; i <= q; i++){
			if(in[i] == 0) Q.push(i);
		}
		vector<int> p;
		while(!Q.empty()){
			int v = Q.front();
			Q.pop();
			p.push_back(v);
			for(auto x : G[v]){
				in[x]--;
				if(in[x] == 0) Q.push(x);
			}
		}
		if(p.size() != q) ok = 0;
		cout << (ok ? "Yes" : "No") << '\n';
	}
}

Compilation message

jail.cpp:4:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    4 | main(){
      | ^~~~
jail.cpp: In function 'int main()':
jail.cpp:68:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |   if(p.size() != q) ok = 0;
      |      ~~~~~~~~~^~~~

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Incorrect	18 ms	596 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #2

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Incorrect	3 ms	340 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3

0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Incorrect	3 ms	340 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #4

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Incorrect	3 ms	340 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #5

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Incorrect	3 ms	340 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #6

0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	0 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Incorrect	11 ms	340 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #7

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Incorrect	18 ms	596 KB	Output isn't correct
5	Halted	0 ms	0 KB	-