oj.uz

Submission #971893

# Submission time Handle Problem Language Result Execution time Memory
971893 2024-04-29T12:51:32 Z happy_node Jail (JOI22_jail) C++17
0 / 100
 1886 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, par[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;

		dep[1]=1;
		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 13 ms 28764 KB Output is correct
2 Correct 12 ms 28656 KB Output is correct
3 Correct 13 ms 28464 KB Output is correct
4 Correct 15 ms 31072 KB Output is correct
5 Correct 22 ms 31584 KB Output is correct
6 Correct 9 ms 30812 KB Output is correct
7 Correct 19 ms 37468 KB Output is correct
8 Correct 11 ms 37720 KB Output is correct
9 Correct 142 ms 48852 KB Output is correct
10 Correct 565 ms 284120 KB Output is correct
11 Correct 15 ms 30948 KB Output is correct
12 Correct 45 ms 31844 KB Output is correct
13 Correct 200 ms 116572 KB Output is correct
14 Correct 229 ms 146728 KB Output is correct
15 Runtime error 1886 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 14 ms 28508 KB Output is correct
2 Correct 17 ms 28680 KB Output is correct
3 Correct 15 ms 29020 KB Output is correct
4 Incorrect 14 ms 30228 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28508 KB Output is correct
2 Correct 17 ms 28680 KB Output is correct
3 Correct 15 ms 29020 KB Output is correct
4 Incorrect 14 ms 30228 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28508 KB Output is correct
2 Correct 17 ms 28680 KB Output is correct
3 Correct 15 ms 29020 KB Output is correct
4 Incorrect 14 ms 30228 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28508 KB Output is correct
2 Correct 17 ms 28680 KB Output is correct
3 Correct 15 ms 29020 KB Output is correct
4 Incorrect 14 ms 30228 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 37216 KB Output is correct
3 Correct 12 ms 30308 KB Output is correct
4 Correct 16 ms 28512 KB Output is correct
5 Correct 20 ms 28676 KB Output is correct
6 Incorrect 15 ms 28512 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28764 KB Output is correct
2 Correct 12 ms 28656 KB Output is correct
3 Correct 13 ms 28464 KB Output is correct
4 Correct 15 ms 31072 KB Output is correct
5 Correct 22 ms 31584 KB Output is correct
6 Correct 9 ms 30812 KB Output is correct
7 Correct 19 ms 37468 KB Output is correct
8 Correct 11 ms 37720 KB Output is correct
9 Correct 142 ms 48852 KB Output is correct
10 Correct 565 ms 284120 KB Output is correct
11 Correct 15 ms 30948 KB Output is correct
12 Correct 45 ms 31844 KB Output is correct
13 Correct 200 ms 116572 KB Output is correct
14 Correct 229 ms 146728 KB Output is correct
15 Runtime error 1886 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -