oj.uz

답안 #567242

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
567242 2022-05-23T09:42:13 Z jamielim Jail (JOI22_jail) C++14
0 / 100
 14 ms 9288 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;

int q,n,m;

int fw[120005];
void upd(int x,int y){
	y++;
	while(y<=n){
		fw[y]--;
		y+=y&(-y);
	}
	while(x<=n){
		fw[x]++;
		x+=x&(-x);
	}
}
int qry(int x){
	int res=0;
	while(x){
		res+=fw[x];
		x-=x&(-x);
	}
	return res;
}

vector<int> adj[120005];
set<int> dag[120005];
ii arr[120005];

int dep[120005];
int par[20][120005];

void dfs(int x,int p){
	par[0][x]=p;
	for(int i:adj[x]){
		if(p==i)continue;
		dep[i]=dep[x]+1;
		dfs(i,x);
	}
}

int lca(int x,int y){
	if(x==y)return x;
	if(dep[x]>dep[y])swap(x,y);
	for(int i=19;i>=0;i--){
		if(dep[x]<=dep[par[i][y]])y=par[i][y];
	}
	if(x==y)return x;
	for(int i=19;i>=0;i--){
		if(par[i][x]!=par[i][y])x=par[i][x],y=par[i][y];
	}
	return par[0][x];
}

int dist(int x,int y){
	int l=lca(x,y);
	int ans=0;
	for(int i=19;i>=0;i--){
		if(dep[par[i][x]]>=dep[l]){
			x=par[i][x];
			ans+=(1<<i);
		}
	}
	for(int i=19;i>=0;i--){
		if(dep[par[i][y]]>=dep[l]){
			y=par[i][y];
			ans+=(1<<i);
		}
	}
	return ans;
}

vector<int> topo;
int vis[120005];
void toposort(int x){
	vis[x]=1;
	for(int i:dag[x]){
		if(vis[i])continue;
		toposort(i);
	}
	topo.pb(x);
}

int main(){
	scanf("%d",&q);
	while(q--){
		scanf("%d",&n);
		int a,b;
		bool st1=1;
		for(int i=1;i<n;i++){
			scanf("%d%d",&a,&b);
			adj[a].pb(b);adj[b].pb(a);
			if(a!=i||b!=i+1)st1=0;
		}
		scanf("%d",&m);
		for(int i=1;i<=m;i++)scanf("%d%d",&arr[i].fi,&arr[i].se);
		if(st1){
			bool die=0;
			vector<ii> v1,v2;
			for(int i=1;i<=m;i++){
				if(arr[i].fi<=arr[i].se){
					v1.pb(arr[i].fi,arr[i].se);
					upd(arr[i].fi,arr[i].se);
				}else{
					v2.pb(arr[i].se,arr[i].fi);
				}
			}
			for(int i=1;i<=m;i++){
				if(arr[i].fi>arr[i].se){
					if(qry(arr[i].se)){
						die=1;
					}
				}
			}
			sort(ALL(v1));sort(ALL(v2));
			for(int i=1;i<SZ(v1);i++){
				if(v1[i].se<v1[i-1].se)die=1;
			}
			for(int i=1;i<SZ(v2);i++){
				if(v2[i].se<v2[i-1].se)die=1;
			}
			if(die)printf("No\n");
			else printf("Yes\n");
			for(int i=0;i<=n+2;i++)fw[i]=0;
		}else{
			if(q<=20&&m<=500){
				dfs(1,0);
				dep[0]=-INF;
				for(int i=1;i<20;i++){
					for(int j=1;j<=n;j++){
						par[i][j]=par[i-1][par[i-1][j]];
					}
				}
				int indeg[n+5];memset(indeg,0,sizeof(indeg));
				set<int> ctr;
				for(int i=1;i<=m;i++){
					int d=dist(arr[i].fi,arr[i].se);
					for(int j=1;j<=m;j++){
						if(i==j)continue;
						if(d==dist(arr[i].fi,arr[j].se)+dist(arr[i].se,arr[j].se)){
							// j is on path of i => i is before j
							dag[i].insert(j);
							indeg[j]++;
							ctr.insert(i);ctr.insert(j);
						}
					}
				}
				for(int i=1;i<=n;i++)if(indeg[i]==0)toposort(i);
				reverse(ALL(topo));
				bool die=0;
				for(int i=1;i<=SZ(topo);i++){
					int x=topo[i];
					ctr.erase(x);
					for(int j=i+1;j<=m;j++){
						int y=topo[j];
						if(dag[y].find(x)!=dag[y].end()){ // y is supposed to be before x
							die=1;
						}
					}
				}
				if(die||SZ(ctr)!=0){
					printf("No\n");
				}else{
					printf("Yes\n");
				}
				topo.clear();
				memset(vis,0,sizeof(vis));
			}
		}
		for(int i=1;i<=n;i++)adj[i].clear();
		for(int i=1;i<=m;i++)dag[i].clear();
	}
}

Compilation message

jail.cpp: In function 'int main()':
jail.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
jail.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |   scanf("%d",&n);
      |   ~~~~~^~~~~~~~~
jail.cpp:107:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |    scanf("%d%d",&a,&b);
      |    ~~~~~^~~~~~~~~~~~~~
jail.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   scanf("%d",&m);
      |   ~~~~~^~~~~~~~~
jail.cpp:112:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   for(int i=1;i<=m;i++)scanf("%d%d",&arr[i].fi,&arr[i].se);
      |                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8660 KB Output is correct
2 Correct 5 ms 8788 KB Output is correct
3 Correct 4 ms 8660 KB Output is correct
4 Incorrect 14 ms 9024 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8772 KB Output is correct
2 Correct 4 ms 8660 KB Output is correct
3 Incorrect 7 ms 8824 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8772 KB Output is correct
2 Correct 4 ms 8660 KB Output is correct
3 Incorrect 7 ms 8824 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8772 KB Output is correct
2 Correct 4 ms 8660 KB Output is correct
3 Incorrect 7 ms 8824 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8772 KB Output is correct
2 Correct 4 ms 8660 KB Output is correct
3 Incorrect 7 ms 8824 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8788 KB Output is correct
2 Correct 5 ms 9288 KB Output is correct
3 Correct 6 ms 8820 KB Output is correct
4 Correct 6 ms 8660 KB Output is correct
5 Incorrect 10 ms 8788 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8660 KB Output is correct
2 Correct 5 ms 8788 KB Output is correct
3 Correct 4 ms 8660 KB Output is correct
4 Incorrect 14 ms 9024 KB Output isn't correct
5 Halted 0 ms 0 KB -