Submission #1102780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102780		Bula	Jail (JOI22_jail)	C++17	77 / 100	5105 ms	514768 KiB

jail

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

main(){
	int tt = 1; cin >> tt;
	while(tt--){
		int n;
		cin >> n;
		int c = 1;
		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);
			if(x != i || y != i + 1) c = 0;
		}
		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<pair<int, int>> A, B;
		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);
			A.push_back({a[i], i});
			B.push_back({b[i], i});
		}
		int ok = 1;
		if(c == 1){
			sort(A.begin(), A.end());
			sort(B.begin(), B.end());
			for(int i = 0; i < q; i++){
				if(A[i].second != B[i].second) ok = 0;
			}
		}else{
			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]){
						if(u == i) continue;
						G[u].push_back(i);
						in[i]++;
						m[u]++;
						if(m[u] == 2) ok = 0;
					}
					x = par[x];
				}
				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]){
					if(u == i) continue;
					G[u].push_back(i);
					in[i]++;
					m[u]++;
					if(m[u] == 2) ok = 0;
				}
			}
			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:97:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |    if(p.size() != q) ok = 0;
      |       ~~~~~~~~~^~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 0 / 23