oj.uz

Submission #975300

# Submission time Handle Problem Language Result Execution time Memory
975300 2024-05-04T17:36:22 Z happy_node Jail (JOI22_jail) C++17
5 / 100
 1212 ms 321700 KB 
#include <bits/stdc++.h>
using namespace std;

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

vector<int> adj[MX], cyc[MX*40];

int up[MX][20], dep[MX], deg[MX*40];

int timer=0,tin[MX],tout[MX];

int valS[MX], valT[MX];

int idS[MX][20], idT[MX][20];

void dfs(int v, int p) {
	tin[v]=++timer;
	up[v][0]=p;
	for(int k=1;k<18;k++) {
		up[v][k]=up[up[v][k-1]][k-1];
	}
	for(auto u:adj[v]) {
		if(u==p) continue;
		dep[u]=dep[v]+1;
		dfs(u,v);
	}
	tout[v]=timer;
}

bool isAnc(int u, int v) { // u is the ancestor
	return tin[u]<=tin[v] && tout[v]<=tout[u];
}

int getLCA(int u, int v) {
	if(isAnc(u,v)) return u;
	if(isAnc(v,u)) return v;

	for(int k=0;k<18;k++) {
		if(up[u][k]!=0 && !isAnc(up[u][k],v)) {
			u=up[u][k];
		}
	}
	return up[u][0];
}

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

	cin>>Q;

	while(Q--) {
		cin>>N;

		for(int i=1;i<=N;i++) {
			valS[i]=-1;
			valT[i]=-1;
			dep[i]=0;
			adj[i].clear();

			for(int j=0;j<18;j++) {
				up[i][j]=0;
				idS[i][j]=0;
				idT[i][j]=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);
		}

		tin[0]=0;
		tout[0]=1e9;

		timer=0;
		dfs(1,0);

		cin>>M;

		int id=M;
		for(int i=1;i<=N;i++) {
			for(int j=0;j<18;j++) {
				idS[i][j]=id++;
			}
		}
		for(int i=1;i<=N;i++) {
			for(int j=0;j<18;j++) {
				idT[i][j]=id++;
			}
		}
		for(int i=1;i<=N;i++) {
			for(int j=0;j<17;j++) {
				cyc[idS[i][j]].push_back(idS[i][j+1]);
				if(j>0 && up[i][j-1]!=0) cyc[idS[up[i][j-1]][j]].push_back(idS[i][j+1]);

				cyc[idT[i][j+1]].push_back(idT[i][j]);
				if(j>0 && up[i][j-1]!=0) cyc[idT[i][j+1]].push_back(idT[up[i][j-1]][j]);
			}
		}

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

			valS[S[i]]=i;
			valT[T[i]]=i;
		}
		for(int i=0;i<M;i++) {
			int L=getLCA(S[i],T[i]);

			// everything within par(S[i]) to before L don't have tricky cases
			if(dep[S[i]]-dep[L]>=2) {
				int v=up[S[i]][0];
				for(int k=16;k>=0;k--) {
					if(up[v][k]!=0 && !isAnc(up[v][k],L)) {
						cyc[idS[v][k+1]].push_back(i);
						cyc[i].push_back(idT[v][k+1]);
						v=up[v][k];
					}
				}
				cyc[idS[v][0]].push_back(i);
				cyc[i].push_back(idT[v][0]);
			}
			if(dep[T[i]]-dep[L]>=2) {
				int v=up[T[i]][0];
				for(int k=16;k>=0;k--) {
					if(up[v][k]!=0 && !isAnc(up[v][k],L)) {
						cyc[idS[v][k+1]].push_back(i);
						cyc[i].push_back(idT[v][k+1]);
						v=up[v][k];
					}
				}
				cyc[idS[v][0]].push_back(i);
				cyc[i].push_back(idT[v][0]);
			}

			// connect to the base
			cyc[i].push_back(idS[S[i]][0]);
			cyc[idT[T[i]][0]].push_back(i);

			// this is for handling the cases on the edge to make sure 
			// we don't connect i with itself
			vector<int> cands={S[i],L,T[i]};
			for(auto x:cands) {
				// we just naively connect edges since there are <= 3 candidates
				if(valS[x]!=-1 && valS[x]!=i) cyc[valS[x]].push_back(i);
				if(valT[x]!=-1 && valT[x]!=i) cyc[i].push_back(valT[x]);
			}
		}

		for(int i=0;i<id;i++) {
			for(auto j:cyc[i]) {
				deg[j]+=1;
			}
		}

		queue<int> q;
		for(int i=0;i<id;i++) {
			if(!deg[i]) q.push(i);
		}

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

		cout<<(ans==id?"Yes":"No")<<'\n';

		for(int i=0;i<id;i++) {
			cyc[i].clear();
			deg[i]=0;
		}
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 117844 KB Output is correct
2 Correct 38 ms 117844 KB Output is correct
3 Correct 39 ms 117728 KB Output is correct
4 Correct 75 ms 118660 KB Output is correct
5 Correct 110 ms 118912 KB Output is correct
6 Correct 43 ms 118216 KB Output is correct
7 Correct 43 ms 118364 KB Output is correct
8 Correct 44 ms 118452 KB Output is correct
9 Correct 217 ms 129004 KB Output is correct
10 Correct 872 ms 304728 KB Output is correct
11 Correct 55 ms 118096 KB Output is correct
12 Correct 125 ms 118928 KB Output is correct
13 Correct 968 ms 309724 KB Output is correct
14 Correct 801 ms 309836 KB Output is correct
15 Correct 883 ms 311484 KB Output is correct
16 Correct 1212 ms 321700 KB Output is correct
17 Correct 1130 ms 312640 KB Output is correct
18 Correct 877 ms 314728 KB Output is correct
19 Correct 1004 ms 312720 KB Output is correct
20 Correct 937 ms 312712 KB Output is correct
21 Correct 855 ms 314504 KB Output is correct
22 Correct 779 ms 309828 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 117836 KB Output is correct
2 Correct 42 ms 117848 KB Output is correct
3 Correct 51 ms 118576 KB Output is correct
4 Incorrect 49 ms 118196 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 117836 KB Output is correct
2 Correct 42 ms 117848 KB Output is correct
3 Correct 51 ms 118576 KB Output is correct
4 Incorrect 49 ms 118196 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 117836 KB Output is correct
2 Correct 42 ms 117848 KB Output is correct
3 Correct 51 ms 118576 KB Output is correct
4 Incorrect 49 ms 118196 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 117836 KB Output is correct
2 Correct 42 ms 117848 KB Output is correct
3 Correct 51 ms 118576 KB Output is correct
4 Incorrect 49 ms 118196 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 117804 KB Output is correct
2 Correct 42 ms 117840 KB Output is correct
3 Correct 41 ms 117852 KB Output is correct
4 Correct 41 ms 117844 KB Output is correct
5 Correct 55 ms 117980 KB Output is correct
6 Correct 44 ms 118292 KB Output is correct
7 Correct 42 ms 118352 KB Output is correct
8 Incorrect 40 ms 117840 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 117844 KB Output is correct
2 Correct 38 ms 117844 KB Output is correct
3 Correct 39 ms 117728 KB Output is correct
4 Correct 75 ms 118660 KB Output is correct
5 Correct 110 ms 118912 KB Output is correct
6 Correct 43 ms 118216 KB Output is correct
7 Correct 43 ms 118364 KB Output is correct
8 Correct 44 ms 118452 KB Output is correct
9 Correct 217 ms 129004 KB Output is correct
10 Correct 872 ms 304728 KB Output is correct
11 Correct 55 ms 118096 KB Output is correct
12 Correct 125 ms 118928 KB Output is correct
13 Correct 968 ms 309724 KB Output is correct
14 Correct 801 ms 309836 KB Output is correct
15 Correct 883 ms 311484 KB Output is correct
16 Correct 1212 ms 321700 KB Output is correct
17 Correct 1130 ms 312640 KB Output is correct
18 Correct 877 ms 314728 KB Output is correct
19 Correct 1004 ms 312720 KB Output is correct
20 Correct 937 ms 312712 KB Output is correct
21 Correct 855 ms 314504 KB Output is correct
22 Correct 779 ms 309828 KB Output is correct
23 Correct 42 ms 117836 KB Output is correct
24 Correct 42 ms 117848 KB Output is correct
25 Correct 51 ms 118576 KB Output is correct
26 Incorrect 49 ms 118196 KB Output isn't correct
27 Halted 0 ms 0 KB -