oj.uz

Submission #570403

# Submission time Handle Problem Language Result Execution time Memory
570403 2022-05-29T13:30:23 Z jamezzz Jail (JOI22_jail) C++17
21 / 100
 1753 ms 358448 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 k=0;k<20;++k){
			par[i][k]=0;
		}
	}
	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;
		if(a!=b)l=par[a][0];
		else l=a;
		
		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:113:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |   int a,b;sf("%d%d",&a,&b);
      |             ^
jail.cpp:117:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |  sf("%d",&m);
      |    ^
jail.cpp:119:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |   sf("%d%d",&s[i],&t[i]);
      |     ^
jail.cpp: In function 'int main()':
jail.cpp:225:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  225 |  int tc;sf("%d",&tc);
      |           ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 144052 KB Output is correct
2 Correct 74 ms 144008 KB Output is correct
3 Correct 77 ms 144020 KB Output is correct
4 Correct 95 ms 144368 KB Output is correct
5 Correct 133 ms 144308 KB Output is correct
6 Correct 75 ms 144236 KB Output is correct
7 Correct 89 ms 144276 KB Output is correct
8 Correct 73 ms 144356 KB Output is correct
9 Correct 335 ms 151756 KB Output is correct
10 Correct 707 ms 324560 KB Output is correct
11 Correct 92 ms 144128 KB Output is correct
12 Correct 156 ms 144404 KB Output is correct
13 Correct 729 ms 329984 KB Output is correct
14 Correct 795 ms 329976 KB Output is correct
15 Correct 1626 ms 350776 KB Output is correct
16 Correct 1753 ms 345696 KB Output is correct
17 Correct 681 ms 333632 KB Output is correct
18 Correct 682 ms 333304 KB Output is correct
19 Correct 764 ms 333548 KB Output is correct
20 Correct 713 ms 333516 KB Output is correct
21 Correct 1002 ms 358448 KB Output is correct
22 Correct 700 ms 328860 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 143992 KB Output is correct
2 Correct 83 ms 144160 KB Output is correct
3 Correct 101 ms 144288 KB Output is correct
4 Correct 76 ms 144216 KB Output is correct
5 Correct 75 ms 144176 KB Output is correct
6 Correct 78 ms 144216 KB Output is correct
7 Correct 79 ms 144284 KB Output is correct
8 Correct 85 ms 144204 KB Output is correct
9 Correct 78 ms 144280 KB Output is correct
10 Correct 74 ms 144244 KB Output is correct
11 Correct 79 ms 144204 KB Output is correct
12 Correct 81 ms 144156 KB Output is correct
13 Correct 79 ms 144244 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 143992 KB Output is correct
2 Correct 83 ms 144160 KB Output is correct
3 Correct 101 ms 144288 KB Output is correct
4 Correct 76 ms 144216 KB Output is correct
5 Correct 75 ms 144176 KB Output is correct
6 Correct 78 ms 144216 KB Output is correct
7 Correct 79 ms 144284 KB Output is correct
8 Correct 85 ms 144204 KB Output is correct
9 Correct 78 ms 144280 KB Output is correct
10 Correct 74 ms 144244 KB Output is correct
11 Correct 79 ms 144204 KB Output is correct
12 Correct 81 ms 144156 KB Output is correct
13 Correct 79 ms 144244 KB Output is correct
14 Correct 76 ms 144016 KB Output is correct
15 Correct 79 ms 144040 KB Output is correct
16 Correct 89 ms 144268 KB Output is correct
17 Correct 78 ms 144248 KB Output is correct
18 Correct 73 ms 144300 KB Output is correct
19 Correct 77 ms 144000 KB Output is correct
20 Correct 76 ms 144308 KB Output is correct
21 Correct 76 ms 144200 KB Output is correct
22 Correct 84 ms 144252 KB Output is correct
23 Correct 80 ms 144032 KB Output is correct
24 Correct 76 ms 144032 KB Output is correct
25 Incorrect 89 ms 144240 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 143992 KB Output is correct
2 Correct 83 ms 144160 KB Output is correct
3 Correct 101 ms 144288 KB Output is correct
4 Correct 76 ms 144216 KB Output is correct
5 Correct 75 ms 144176 KB Output is correct
6 Correct 78 ms 144216 KB Output is correct
7 Correct 79 ms 144284 KB Output is correct
8 Correct 85 ms 144204 KB Output is correct
9 Correct 78 ms 144280 KB Output is correct
10 Correct 74 ms 144244 KB Output is correct
11 Correct 79 ms 144204 KB Output is correct
12 Correct 81 ms 144156 KB Output is correct
13 Correct 79 ms 144244 KB Output is correct
14 Correct 76 ms 144016 KB Output is correct
15 Correct 79 ms 144040 KB Output is correct
16 Correct 89 ms 144268 KB Output is correct
17 Correct 78 ms 144248 KB Output is correct
18 Correct 73 ms 144300 KB Output is correct
19 Correct 77 ms 144000 KB Output is correct
20 Correct 76 ms 144308 KB Output is correct
21 Correct 76 ms 144200 KB Output is correct
22 Correct 84 ms 144252 KB Output is correct
23 Correct 80 ms 144032 KB Output is correct
24 Correct 76 ms 144032 KB Output is correct
25 Incorrect 89 ms 144240 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 143992 KB Output is correct
2 Correct 83 ms 144160 KB Output is correct
3 Correct 101 ms 144288 KB Output is correct
4 Correct 76 ms 144216 KB Output is correct
5 Correct 75 ms 144176 KB Output is correct
6 Correct 78 ms 144216 KB Output is correct
7 Correct 79 ms 144284 KB Output is correct
8 Correct 85 ms 144204 KB Output is correct
9 Correct 78 ms 144280 KB Output is correct
10 Correct 74 ms 144244 KB Output is correct
11 Correct 79 ms 144204 KB Output is correct
12 Correct 81 ms 144156 KB Output is correct
13 Correct 79 ms 144244 KB Output is correct
14 Correct 76 ms 144016 KB Output is correct
15 Correct 79 ms 144040 KB Output is correct
16 Correct 89 ms 144268 KB Output is correct
17 Correct 78 ms 144248 KB Output is correct
18 Correct 73 ms 144300 KB Output is correct
19 Correct 77 ms 144000 KB Output is correct
20 Correct 76 ms 144308 KB Output is correct
21 Correct 76 ms 144200 KB Output is correct
22 Correct 84 ms 144252 KB Output is correct
23 Correct 80 ms 144032 KB Output is correct
24 Correct 76 ms 144032 KB Output is correct
25 Incorrect 89 ms 144240 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 144012 KB Output is correct
2 Correct 85 ms 144076 KB Output is correct
3 Correct 70 ms 144060 KB Output is correct
4 Correct 73 ms 144064 KB Output is correct
5 Correct 88 ms 144108 KB Output is correct
6 Correct 70 ms 144180 KB Output is correct
7 Correct 72 ms 144204 KB Output is correct
8 Correct 86 ms 144024 KB Output is correct
9 Correct 76 ms 144012 KB Output is correct
10 Correct 74 ms 144128 KB Output is correct
11 Correct 71 ms 144076 KB Output is correct
12 Correct 72 ms 144180 KB Output is correct
13 Correct 119 ms 144608 KB Output is correct
14 Correct 140 ms 144952 KB Output is correct
15 Correct 119 ms 144948 KB Output is correct
16 Correct 375 ms 214572 KB Output is correct
17 Correct 663 ms 225420 KB Output is correct
18 Correct 816 ms 243400 KB Output is correct
19 Correct 496 ms 216332 KB Output is correct
20 Correct 504 ms 214220 KB Output is correct
21 Correct 455 ms 214724 KB Output is correct
22 Correct 575 ms 223228 KB Output is correct
23 Correct 499 ms 221268 KB Output is correct
24 Correct 542 ms 219704 KB Output is correct
25 Correct 473 ms 220432 KB Output is correct
26 Correct 519 ms 221928 KB Output is correct
27 Correct 420 ms 209860 KB Output is correct
28 Correct 440 ms 218652 KB Output is correct
29 Correct 469 ms 213996 KB Output is correct
30 Correct 422 ms 207472 KB Output is correct
31 Correct 411 ms 207940 KB Output is correct
32 Correct 403 ms 205880 KB Output is correct
33 Correct 442 ms 207684 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 144052 KB Output is correct
2 Correct 74 ms 144008 KB Output is correct
3 Correct 77 ms 144020 KB Output is correct
4 Correct 95 ms 144368 KB Output is correct
5 Correct 133 ms 144308 KB Output is correct
6 Correct 75 ms 144236 KB Output is correct
7 Correct 89 ms 144276 KB Output is correct
8 Correct 73 ms 144356 KB Output is correct
9 Correct 335 ms 151756 KB Output is correct
10 Correct 707 ms 324560 KB Output is correct
11 Correct 92 ms 144128 KB Output is correct
12 Correct 156 ms 144404 KB Output is correct
13 Correct 729 ms 329984 KB Output is correct
14 Correct 795 ms 329976 KB Output is correct
15 Correct 1626 ms 350776 KB Output is correct
16 Correct 1753 ms 345696 KB Output is correct
17 Correct 681 ms 333632 KB Output is correct
18 Correct 682 ms 333304 KB Output is correct
19 Correct 764 ms 333548 KB Output is correct
20 Correct 713 ms 333516 KB Output is correct
21 Correct 1002 ms 358448 KB Output is correct
22 Correct 700 ms 328860 KB Output is correct
23 Correct 74 ms 143992 KB Output is correct
24 Correct 83 ms 144160 KB Output is correct
25 Correct 101 ms 144288 KB Output is correct
26 Correct 76 ms 144216 KB Output is correct
27 Correct 75 ms 144176 KB Output is correct
28 Correct 78 ms 144216 KB Output is correct
29 Correct 79 ms 144284 KB Output is correct
30 Correct 85 ms 144204 KB Output is correct
31 Correct 78 ms 144280 KB Output is correct
32 Correct 74 ms 144244 KB Output is correct
33 Correct 79 ms 144204 KB Output is correct
34 Correct 81 ms 144156 KB Output is correct
35 Correct 79 ms 144244 KB Output is correct
36 Correct 76 ms 144016 KB Output is correct
37 Correct 79 ms 144040 KB Output is correct
38 Correct 89 ms 144268 KB Output is correct
39 Correct 78 ms 144248 KB Output is correct
40 Correct 73 ms 144300 KB Output is correct
41 Correct 77 ms 144000 KB Output is correct
42 Correct 76 ms 144308 KB Output is correct
43 Correct 76 ms 144200 KB Output is correct
44 Correct 84 ms 144252 KB Output is correct
45 Correct 80 ms 144032 KB Output is correct
46 Correct 76 ms 144032 KB Output is correct
47 Incorrect 89 ms 144240 KB Output isn't correct
48 Halted 0 ms 0 KB -