oj.uz

Submission #971890

# Submission time Handle Problem Language Result Execution time Memory
971890 2024-04-29T12:48:45 Z happy_node Jail (JOI22_jail) C++17
0 / 100
 2144 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;

const int MX=4e5+5;
int Q,N,M;
int S[MX], T[MX];

vector<int> path[MX]; // store the path between Si and Ti

vector<int> adj[MX];

int par[MX], dep[MX];

void dfs(int v, int p) {
	par[v]=p;
	for(auto u:adj[v]) {
		if(u==p) continue;
		dep[u]=dep[v]+1;
		dfs(u,v);
	}
}

vector<int> ADJ[MX];
int deg[MX];

bool f(int i, int x) {
	for(auto y:path[i]) 
		if(y==x) return true;
	return false;
}

int cntT[MX], cntS[MX];

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin>>Q;

	while(Q--) {
		cin>>N;
		for(int i=1;i<=N;i++) adj[i].clear(), cntT[i]=0, cntS[i]=0, dep[i]=0;

		for(int i=0;i<N-1;i++) {
			int u,v;
			cin>>u>>v;
			adj[u].push_back(v);
			adj[v].push_back(u);
		}

		cin>>M;
		for(int i=0;i<2*N+M;i++) path[i].clear(), ADJ[i].clear(), deg[i]=0;

		dfs(1,0);

		for(int i=0;i<M;i++) {
			cin>>S[i]>>T[i];

			vector<int> L,R;

			int u=S[i],v=T[i];

			while(dep[u]>dep[v]) {
				L.push_back(u);
				u=par[u];
			}

			while(dep[v]>dep[u]) {
				R.push_back(v);
				v=par[v];
			}

			while(u!=v) {
				L.push_back(u);
				R.push_back(v);
				u=par[u];
				v=par[v];
			}

			for(auto x:L) path[i].push_back(x);
			path[i].push_back(S[i]);
			reverse(R.begin(),R.end());
			for(auto x:R) path[i].push_back(x);
		}

		for(int i=0;i<M;i++) {
			cntS[S[i]]+=1;
			cntT[T[i]]+=1;
		}

		set<pair<int,int>> st;

		for(int i=0;i<M;i++) {
			cntS[S[i]]-=1;
			cntT[T[i]]-=1;

			for(auto x:path[i]) {
				if(cntS[x]) {
					ADJ[M-1+x].push_back(i);
					deg[i]+=1;
				}
				if(cntT[x]) {
					ADJ[i].push_back(M-1+x+N);
					deg[M-1+x+N]+=1;
				}
			}

			ADJ[i].push_back(M-1+S[i]);
			deg[M-1+S[i]]+=1;

			ADJ[M-1+T[i]+N].push_back(i);
			deg[i]+=1;

			cntS[S[i]]+=1;
			cntT[T[i]]+=1;
		}

		queue<int> q;

		for(int i=0;i<2*N+M;i++) {
			if(!deg[i]) {
				q.push(i);
			}
		}

		int ans=0;
		while(!q.empty()) {
			auto v=q.front(); q.pop();
			ans+=1;
			for(auto u:ADJ[v]) {
				deg[u]--;
				if(!deg[u]) q.push(u);
			}
		}

		cout<<(ans==2*N+M?"Yes":"No")<<'\n';
	}


}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 37208 KB Output is correct
2 Correct 9 ms 37212 KB Output is correct
3 Correct 8 ms 37332 KB Output is correct
4 Correct 16 ms 37212 KB Output is correct
5 Correct 21 ms 37424 KB Output is correct
6 Correct 8 ms 37212 KB Output is correct
7 Correct 9 ms 37212 KB Output is correct
8 Correct 10 ms 37464 KB Output is correct
9 Correct 146 ms 56148 KB Output is correct
10 Correct 549 ms 287084 KB Output is correct
11 Correct 12 ms 37464 KB Output is correct
12 Correct 42 ms 37460 KB Output is correct
13 Correct 197 ms 118716 KB Output is correct
14 Correct 204 ms 147872 KB Output is correct
15 Runtime error 2144 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 37468 KB Output is correct
2 Correct 8 ms 37212 KB Output is correct
3 Correct 8 ms 37468 KB Output is correct
4 Incorrect 9 ms 37212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 37468 KB Output is correct
2 Correct 8 ms 37212 KB Output is correct
3 Correct 8 ms 37468 KB Output is correct
4 Incorrect 9 ms 37212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 37468 KB Output is correct
2 Correct 8 ms 37212 KB Output is correct
3 Correct 8 ms 37468 KB Output is correct
4 Incorrect 9 ms 37212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 37468 KB Output is correct
2 Correct 8 ms 37212 KB Output is correct
3 Correct 8 ms 37468 KB Output is correct
4 Incorrect 9 ms 37212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 37212 KB Output is correct
2 Correct 9 ms 37404 KB Output is correct
3 Correct 9 ms 37388 KB Output is correct
4 Correct 9 ms 37212 KB Output is correct
5 Correct 12 ms 37468 KB Output is correct
6 Incorrect 8 ms 37212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 37208 KB Output is correct
2 Correct 9 ms 37212 KB Output is correct
3 Correct 8 ms 37332 KB Output is correct
4 Correct 16 ms 37212 KB Output is correct
5 Correct 21 ms 37424 KB Output is correct
6 Correct 8 ms 37212 KB Output is correct
7 Correct 9 ms 37212 KB Output is correct
8 Correct 10 ms 37464 KB Output is correct
9 Correct 146 ms 56148 KB Output is correct
10 Correct 549 ms 287084 KB Output is correct
11 Correct 12 ms 37464 KB Output is correct
12 Correct 42 ms 37460 KB Output is correct
13 Correct 197 ms 118716 KB Output is correct
14 Correct 204 ms 147872 KB Output is correct
15 Runtime error 2144 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -