oj.uz

Submission #570396

# Submission time Handle Problem Language Result Execution time Memory
570396 2022-05-29T12:59:42 Z jamezzz Jail (JOI22_jail) C++17
5 / 100
 2195 ms 359872 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));

#define mod 1000000007

inline int add(int a,int b){
	int r=a+b;
	while(r>=mod)r-=mod;
	while(r<0)r+=mod;
	return r;
}

inline int mult(int a,int b){
	return (int)(((ll)(a*b))%mod);
}

inline int rd(){
	int x=0;
	char ch=getchar_unlocked();
	while(!(ch&16))ch=getchar();//keep reading while current character is whitespace
    while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar_unlocked();
	}
	return x;
}

#define maxn 120005

int n,m,s[maxn],t[maxn],sid[maxn],tid[maxn];
int par[maxn][20],snode[maxn][20],tnode[maxn][20],depth[maxn],cnt;
vi AL[maxn],AL2[maxn*50];
int vis[maxn*50];
bool pos=false;

void dfs(int u){
	snode[u][0]=cnt++;
	tnode[u][0]=cnt++;
	if(sid[u]!=-1){
		AL2[sid[u]].pb(snode[u][0]);
		AL2[sid[u]].pb(tnode[u][0]);
		//pf("add: %d %d\n",sid[u],snode[u][0]);
	}
	if(tid[u]!=-1){
		AL2[snode[u][0]].pb(tid[u]);
		AL2[tnode[u][0]].pb(tid[u]);
		//pf("add: %d %d\n",tnode[u][0],tid[u]);
	}
	for(int v:AL[u]){
		if(v==par[u][0])continue;
		par[v][0]=u;
		depth[v]=depth[u]+1;
		dfs(v);
	}
}

void dfs2(int u){
	vis[u]=1;
	for(int v:AL2[u]){
		if(vis[v]==0)dfs2(v);
		else if(vis[v]==1)pos=false;
	}
	vis[u]=2;
}

inline void jump(int &x,int k,int i){
	AL2[snode[x][k]].pb(i);
	//pf("add: %d %d\n",snode[x][k],i);
	AL2[i].pb(tnode[x][k]);
	//pf("add: %d %d\n",i,tnode[x][k]);
	x=par[x][k];
}

void solve(){
	sf("%d",&n);
	for(int i=1;i<=n;++i){
		AL[i].clear();
		sid[i]=tid[i]=-1;
	}
	for(int i=0;i<n-1;++i){
		int a,b;sf("%d%d",&a,&b);
		AL[a].pb(b);
		AL[b].pb(a);
	}
	sf("%d",&m);
	for(int i=0;i<m;++i){
		sf("%d%d",&s[i],&t[i]);
		sid[s[i]]=i;
		tid[t[i]]=i;
	}
	
	cnt=m;
	depth[1]=0;dfs(1);
	
	for(int k=1;k<20;++k){
		for(int i=1;i<=n;++i){
			if(par[i][k-1]!=0){
				par[i][k]=par[par[i][k-1]][k-1];
				snode[i][k]=cnt++;
				tnode[i][k]=cnt++;
				
				AL2[snode[i][k-1]].pb(snode[i][k]);
				AL2[snode[par[i][k-1]][k-1]].pb(snode[i][k]);
				AL2[tnode[i][k]].pb(tnode[i][k-1]);
				AL2[tnode[i][k]].pb(tnode[par[i][k-1]][k-1]);
			}
		}
	}	

	/*
	for(int i=1;i<=n;++i){
		pf("%d: ",i);
		for(int k=0;k<5;++k){
			pf("(%d %d) ",snode[i][k],tnode[i][k]);
		}
		pf("\n");
	}
	*/
	
	
	for(int i=0;i<m;++i){
		int a=s[i],b=t[i];
		if(depth[a]<depth[b])swap(a,b);
		for(int k=19;k>=0;--k){
			if(par[a][k]!=0&&depth[par[a][k]]>=depth[b]){
				a=par[a][k];
			}
		}
		for(int k=19;k>=0;--k){
			if(par[a][k]!=par[b][k]){
				a=par[a][k],b=par[b][k];
			}
		}
		int l=a;
		if(a!=b)l=par[a][0];
		
		a=s[i],b=t[i];
		if(a!=l){
			a=par[a][0];
			for(int k=19;k>=0;--k){
				if(par[a][k]!=0&&depth[par[a][k]]>=depth[l]){
					jump(a,k,i);
				}
			}
		}
		if(b!=l){
			b=par[b][0];
			for(int k=19;k>=0;--k){
				if(par[b][k]!=0&&depth[par[b][k]]>=depth[l]){
					jump(b,k,i);
				}
			}
		}
		if(s[i]!=l&&t[i]!=l){
			AL2[snode[l][0]].pb(i);
			//pf("add: %d %d\n",snode[l][0],i);
			AL2[i].pb(tnode[l][0]);
			//pf("add: %d %d\n",i,tnode[l][0]);
		}
	}
	
	for(int i=0;i<cnt;++i){
		disc(AL2[i]);
	}
	
	/*
	for(int i=0;i<cnt;++i){
		for(int j:AL2[i]){
			pf("(%d %d) ",i,j);
		}
		if(AL2[i].size()!=0)pf("\n");
	}
	*/
	
	for(int i=0;i<cnt;++i){
		vis[i]=0;
	}
	pos=true;
	for(int i=0;i<cnt;++i){
		if(!vis[i])dfs2(i);
	}
	
	if(pos)pf("Yes\n");
	else pf("No\n");
	
	for(int i=0;i<cnt;++i)AL2[i].clear();
}

int main(){
	int tc;sf("%d",&tc);
	while(tc--)solve();
}

Compilation message

jail.cpp: In function 'void solve()':
jail.cpp:104:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |  sf("%d",&n);
      |    ^
jail.cpp:110:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |   int a,b;sf("%d%d",&a,&b);
      |             ^
jail.cpp:114:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |  sf("%d",&m);
      |    ^
jail.cpp:116:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |   sf("%d%d",&s[i],&t[i]);
      |     ^
jail.cpp: In function 'int main()':
jail.cpp:219:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  219 |  int tc;sf("%d",&tc);
      |           ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 143960 KB Output is correct
2 Correct 92 ms 144024 KB Output is correct
3 Correct 77 ms 144004 KB Output is correct
4 Correct 117 ms 144496 KB Output is correct
5 Correct 164 ms 144800 KB Output is correct
6 Correct 80 ms 144228 KB Output is correct
7 Correct 84 ms 144388 KB Output is correct
8 Correct 82 ms 144352 KB Output is correct
9 Correct 414 ms 152708 KB Output is correct
10 Correct 745 ms 325680 KB Output is correct
11 Correct 86 ms 144124 KB Output is correct
12 Correct 184 ms 145072 KB Output is correct
13 Correct 838 ms 331648 KB Output is correct
14 Correct 904 ms 331632 KB Output is correct
15 Correct 1630 ms 343748 KB Output is correct
16 Correct 2195 ms 359872 KB Output is correct
17 Correct 863 ms 335392 KB Output is correct
18 Correct 759 ms 336088 KB Output is correct
19 Correct 881 ms 335368 KB Output is correct
20 Correct 789 ms 335376 KB Output is correct
21 Correct 1130 ms 350404 KB Output is correct
22 Correct 746 ms 330648 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 144028 KB Output is correct
2 Correct 72 ms 144012 KB Output is correct
3 Correct 77 ms 144232 KB Output is correct
4 Incorrect 80 ms 144244 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 144028 KB Output is correct
2 Correct 72 ms 144012 KB Output is correct
3 Correct 77 ms 144232 KB Output is correct
4 Incorrect 80 ms 144244 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 144028 KB Output is correct
2 Correct 72 ms 144012 KB Output is correct
3 Correct 77 ms 144232 KB Output is correct
4 Incorrect 80 ms 144244 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 144028 KB Output is correct
2 Correct 72 ms 144012 KB Output is correct
3 Correct 77 ms 144232 KB Output is correct
4 Incorrect 80 ms 144244 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 143948 KB Output is correct
2 Correct 109 ms 143988 KB Output is correct
3 Correct 76 ms 143948 KB Output is correct
4 Correct 84 ms 144068 KB Output is correct
5 Correct 102 ms 144224 KB Output is correct
6 Correct 77 ms 144176 KB Output is correct
7 Correct 83 ms 144084 KB Output is correct
8 Correct 91 ms 144084 KB Output is correct
9 Incorrect 80 ms 143956 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 143960 KB Output is correct
2 Correct 92 ms 144024 KB Output is correct
3 Correct 77 ms 144004 KB Output is correct
4 Correct 117 ms 144496 KB Output is correct
5 Correct 164 ms 144800 KB Output is correct
6 Correct 80 ms 144228 KB Output is correct
7 Correct 84 ms 144388 KB Output is correct
8 Correct 82 ms 144352 KB Output is correct
9 Correct 414 ms 152708 KB Output is correct
10 Correct 745 ms 325680 KB Output is correct
11 Correct 86 ms 144124 KB Output is correct
12 Correct 184 ms 145072 KB Output is correct
13 Correct 838 ms 331648 KB Output is correct
14 Correct 904 ms 331632 KB Output is correct
15 Correct 1630 ms 343748 KB Output is correct
16 Correct 2195 ms 359872 KB Output is correct
17 Correct 863 ms 335392 KB Output is correct
18 Correct 759 ms 336088 KB Output is correct
19 Correct 881 ms 335368 KB Output is correct
20 Correct 789 ms 335376 KB Output is correct
21 Correct 1130 ms 350404 KB Output is correct
22 Correct 746 ms 330648 KB Output is correct
23 Correct 89 ms 144028 KB Output is correct
24 Correct 72 ms 144012 KB Output is correct
25 Correct 77 ms 144232 KB Output is correct
26 Incorrect 80 ms 144244 KB Output isn't correct
27 Halted 0 ms 0 KB -