oj.uz

답안 #570105

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
570105 2022-05-28T14:36:07 Z jamezzz Jail (JOI22_jail) C++17
0 / 100
 139 ms 256924 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;
vector<int> svec[maxn][20],tvec[maxn][20];
vi AL[maxn],AL2[maxn*50];
int vis[maxn*50];
bool pos=false;

void dfs(int u){
	for(int v:AL[u]){
		if(v==par[u][0])continue;
		par[v][0]=u;
		depth[v]=depth[u]+1;		
		snode[v][0]=cnt++;
		tnode[v][0]=cnt++;
		if(sid[u]!=-1)svec[v][0].pb(sid[u]);
		if(tid[u]!=-1)tvec[v][0].pb(tid[u]);
		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){
	//pf("jump: %d %d %d\n",x,k,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){
			svec[i][k].clear();
			tvec[i][k].clear();
		}
	}
	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++;
				
				for(int x:svec[i][k-1])svec[i][k].pb(x);
				for(int x:tvec[i][k-1])tvec[i][k].pb(x);
				for(int x:svec[par[i][k-1]][k-1])svec[i][k].pb(x);
				for(int x:tvec[par[i][k-1]][k-1])tvec[i][k].pb(x);
			}
		}
	}
	
	for(int i=0;i<cnt;++i){
		AL2[i].clear();
	}
	
	/*
	for(int i=1;i<=n;++i){
		for(int k=0;k<5;++k){
			if(!svec[i][k].empty()){
				pf("svec[%d][%d]: ",i,k);
				for(int x:svec[i][k])pf("%d ",x);
				pf("\n");
			}
			if(!tvec[i][k].empty()){
				pf("tvec[%d][%d]: ",i,k);
				for(int x:tvec[i][k])pf("%d ",x);
				pf("\n");
			}
		}
	}
	
	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 k=0;k<20;++k){
		for(int i=1;i<=n;++i){
			for(int x:svec[i][k])AL2[x].pb(snode[i][k]);//,pf("add0: %d %d\n",x,snode[i][k]);
			for(int x:tvec[i][k])AL2[tnode[i][k]].pb(x);//,pf("add0: %d %d\n",tnode[i][k],x);
		}
	}
	
	
	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]){
				jump(a,k,i);
			}
		}
		if(par[a][0]==b)continue;
		for(int k=19;k>=0;--k){
			if(par[a][k]!=par[b][k]){
				jump(a,k,i);
				jump(b,k,i);
			}
		}
		if(sid[a]!=-1&&tid[a]!=-1){
			AL2[sid[a]].pb(tid[a]);
		}
	}
	
	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");
}

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

Compilation message

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

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 256768 KB Output is correct
2 Correct 118 ms 256804 KB Output is correct
3 Incorrect 114 ms 256692 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 256924 KB Output is correct
2 Incorrect 131 ms 256692 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 256924 KB Output is correct
2 Incorrect 131 ms 256692 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 256924 KB Output is correct
2 Incorrect 131 ms 256692 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 256924 KB Output is correct
2 Incorrect 131 ms 256692 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 256712 KB Output is correct
2 Correct 123 ms 256872 KB Output is correct
3 Correct 127 ms 256728 KB Output is correct
4 Incorrect 139 ms 256748 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 256768 KB Output is correct
2 Correct 118 ms 256804 KB Output is correct
3 Incorrect 114 ms 256692 KB Output isn't correct
4 Halted 0 ms 0 KB -