제출 #1327019

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1327019		salmon	Jail (JOI22_jail)	C++20	100 / 100	1002 ms	61960 KiB

jail

#include <bits/stdc++.h>
using namespace std;

int Q;
int N,M;
vector<int> adjlst[120100];
int sise[120100];
int dp[120100];
int pre[120100];
int post[120100];
int parent[120100];
int s[120100];
int t[120100];
int cont = 0;
int pcont0[120100];
int pcont1[120100];
int rcont[120100];
queue<int> q;
int inf = 1.0e9;

struct pu{
	
	int s, e, m;
	int v;
	vector<int> vec;
	pu *l, *r;
	
	pu(int S, int E){
		s = S;
		e = E;
		m = (s + e)/2;
		
		v = 0;
		
		if(s != e){
			l = new pu(s,m);
			r = new pu(m + 1, e);
		}
	}
	
	void set(int S, int E, int i){
		if(S <= s && e <= E){
			vec.push_back(i);
			return;
		}
		
		if(S <= m) l -> set(S,E,i);
		if(m < E) r -> set(S,E,i);
	}
	
	void add(int i){
		if(v == 1){
			for(int j : vec){
				pcont1[j]++;
			}
		}
		else if(v == 0){
			for(int j : vec){
				pcont0[j]++;
			}
		}
		v++;
		
		if(s != e){
			if(i <= m) l -> add(i);
			else r -> add(i);
		}
	}
	
	void rmv(int i){
		if(v == 2){
			for(int j : vec){
				pcont1[j]--;
				if(pcont1[j] == 0 && pcont0[j] == 1 && rcont[j] == 0) q.push(j);
			}
		}
		else if(v == 1){
			for(int j : vec){
				pcont0[j]--;
				if(pcont1[j] == 0 && pcont0[j] == 1 && rcont[j] == 0) q.push(j);
			}
		}
		v--;
		
		if(s != e){
			if(i <= m) l -> rmv(i);
			else r -> rmv(i);
		}
	}
} *root;

struct ru{
	
	int s,e,m;
	int it = -1;
	pair<int,int> v;
	int lazy = 0;
	ru *l, *r;
	
	ru(int S, int E){
		s = S;
		e = E;
		m = (s + e)/2;
		
		v = {0,s};
		
		if(s != e){
			l = new ru(s,m);
			r = new ru(m + 1,e);
		}
	}
	
	void setit(int i, int k){
		if(s == e){
			it = k;
			return;
		}
		
		if(i <= m) l -> setit(i,k);
		else r -> setit(i,k);
	}
	
	void add(int S, int E){
		if(S <= s && e <= E){
			lazy++;
			v.first++;
			return;
		}
		
		if(S <= m) l -> add(S,E);
		if(m < E) r -> add(S,E);
	
		v = min(l -> v, r -> v);
		v.first += lazy;
	}
	
	void activate(int k){
		k += lazy;
		
		if(s == e){
			if(k >= 2 && it != -1) rcont[it] = 1;
			return;
		}
		
		l -> activate(k);
		r -> activate(k);
	}
	
	void rmv(int S,int E){
		if(S <= s && e <= E){
			lazy--;
			v.first--;
			return;
		}
		
		if(S <= m) l -> rmv(S,E);
		if(m < E) r -> rmv(S,E);
		
		v = min(l -> v, r -> v);
		v.first += lazy;
	}
	
	void aa(int i){
		if(s == e){
			v.first = inf;
			if(it != -1){
				rcont[it] = 0;
				if(rcont[it] == 0 && pcont0[it] == 1 && pcont1[it] == 0) q.push(it);
			}
			return;
		}
		
		if(i <= m) l -> aa(i);
		else r -> aa(i);
		
		v = min(l -> v, r -> v);
		v.first += lazy;
	}
	
} *root1;

void dfs(int i, int p){
	sise[i] = 1;
	parent[i] = p;
	
	for(int j : adjlst[i]){
		if(j == p) continue;
		
		dfs(j,i);
		
		sise[i] += sise[j];
	}
}

void dfs1(int i, int p, bool flag){
	if(flag) dp[i] = dp[p];
	else dp[i] = i;
	
	pair<int,int> ii = {-1,-1};
	
	for(int j : adjlst[i]){
		if(j == p) continue;
		
		ii = max(make_pair(sise[j],j),ii);
	}
	
	pre[i] = cont;
	cont++;
	
	if(ii.second != -1) dfs1(ii.second,i,1);
	
	for(int j : adjlst[i]){
		if(j == p) continue;
		if(j == ii.second) continue;
		dfs1(j,i,0);
	}
	
	post[i] = cont-1;
}

vector<pair<int,int>> hld(int u, int v){
	vector<pair<int,int>> vec;
	
	while(true){
		if(pre[u] > pre[v]) swap(u,v);

		if(dp[u] == dp[v]){
			vec.push_back({pre[u],pre[v]});
			break;
		}
		
		vec.push_back({pre[dp[v]],pre[v]});
		v = parent[dp[v]];
	}
	
	return vec;
}

int main(){
	
	scanf(" %d",&Q);
	
	while(Q--){
		
		scanf(" %d",&N);
		
		for(int i = 1; i <= N; i++) adjlst[i].clear();
		while(!q.empty()) q.pop();
		cont = 0;
		
		for(int i = 1; i <= N - 1; i++){
			int u,v;
			
			scanf(" %d",&u);
			scanf(" %d",&v);
			
			adjlst[u].push_back(v);
			adjlst[v].push_back(u);
		}
		
		dfs(1,-1);
		dfs1(1,-1,0);
	
	
		scanf(" %d",&M);
		
		for(int i = 1; i <= M; i++){
			scanf(" %d",&s[i]);
			scanf(" %d",&t[i]);
			
			pcont0[i] = 0;
			pcont1[i] = 0;
			rcont[i] = 0;
		}
		
		root = new pu(0,N-1);
		root1 = new ru(0,N-1);
		
		for(int i = 1; i <= M; i++){
			vector<pair<int,int>> vec = hld(s[i],t[i]);
			
			for(pair<int,int> ii : vec) root -> set(ii.first,ii.second,i);
			
			root1 -> setit(pre[t[i]],i);
			for(pair<int,int> ii : vec){
				root1 -> add(ii.first,ii.second);
			}
		}
		
		for(int i = 1; i <= M; i++) root -> add(pre[s[i]]);
		
		root1 -> activate(0);
		
		while(root1 -> v.first <= 1){
			root1 -> aa(root1 -> v.second);
		}
		int num = 0;
		
		while(!q.empty()){
			int i = q.front();
			q.pop();
			num++;
			
			root -> rmv(pre[s[i]]);
			
			vector<pair<int,int>> vec = hld(s[i],t[i]);
			for(pair<int,int> ii : vec) root1 -> rmv(ii.first,ii.second);
			
			while(root1 -> v.first <= 1){
				root1 -> aa(root1 -> v.second);
			}
		}
		
		if(num == M) printf("Yes\n");
		else printf("No\n");
	}
	
}

컴파일 시 표준 에러 (stderr) 메시지

jail.cpp: In function 'int main()':
jail.cpp:241:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  241 |         scanf(" %d",&Q);
      |         ~~~~~^~~~~~~~~~
jail.cpp:245:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  245 |                 scanf(" %d",&N);
      |                 ~~~~~^~~~~~~~~~
jail.cpp:254:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  254 |                         scanf(" %d",&u);
      |                         ~~~~~^~~~~~~~~~
jail.cpp:255:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  255 |                         scanf(" %d",&v);
      |                         ~~~~~^~~~~~~~~~
jail.cpp:265:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  265 |                 scanf(" %d",&M);
      |                 ~~~~~^~~~~~~~~~
jail.cpp:268:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  268 |                         scanf(" %d",&s[i]);
      |                         ~~~~~^~~~~~~~~~~~~
jail.cpp:269:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  269 |                         scanf(" %d",&t[i]);
      |                         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23