oj.uz

Submission #1102773

# Submission time Handle Problem Language Result Execution time Memory
1102773 2024-10-18T20:29:04 Z Bula Jail (JOI22_jail) C++17
0 / 100
 1 ms 504 KB 
#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 = 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 Incorrect 1 ms 336 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 28.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 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 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Incorrect 1 ms 336 KB Output isn't correct
5 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 Incorrect 1 ms 336 KB Output isn't correct
4 Halted 0 ms 0 KB -