Submission #1102772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102772		Bula	Jail (JOI22_jail)	C++17	0 / 100	18 ms	596 KiB

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 (stderr)

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
• Subtask 2: 0 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23