제출 #942590

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
942590		pcc	Jail (JOI22_jail)	C++17	100 / 100	1483 ms	332304 KiB

jail

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 120010;
vector<int> tree[mxn];
int N,M;
int vcnt,ecnt;
int head[mxn*100],nid[mxn*100],to[mxn*100];
pii arr[mxn];
const int H = 20;

namespace BUILD{
	int newnode(){
		return ++vcnt;
	}
	void add_edge(int a,int b){
		ecnt++;
		nid[ecnt] = head[a];
		to[ecnt] = b;
		head[a] = ecnt;
	}
	int par[mxn][H],dep[mxn];
	int stree[mxn][H],etree[mxn][H];
	int sleaf[mxn],eleaf[mxn];
	void dfs(int now){
		sleaf[now] = newnode();
		eleaf[now] = newnode();
		stree[now][0] = newnode();
		etree[now][0] = newnode();
		add_edge(etree[now][0],eleaf[now]);
		add_edge(etree[now][0],eleaf[par[now][0]]);
		add_edge(sleaf[now],stree[now][0]);
		add_edge(sleaf[par[now][0]],stree[now][0]);
		for(int i = 1;i<H;i++){
			par[now][i] = par[par[now][i-1]][i-1];
			stree[now][i] = newnode();
			etree[now][i] = newnode();
			add_edge(stree[now][i-1],stree[now][i]);
			add_edge(stree[par[now][i-1]][i-1],stree[now][i]);
			add_edge(etree[now][i],etree[now][i-1]);
			add_edge(etree[now][i],etree[par[now][i-1]][i-1]);
		}
		/*
		cerr<<now<<":"<<sleaf[now]<<' '<<eleaf[now]<<endl;;
		for(int i = 0;i<H;i++)cerr<<stree[now][i]<<' ';cerr<<endl;
		for(int i = 0;i<H;i++)cerr<<etree[now][i]<<' ';cerr<<endl;

	   */
		for(auto nxt:tree[now]){
			if(nxt == par[now][0])continue;
			par[nxt][0] = now;
			dep[nxt] = dep[now]+1;
			dfs(nxt);
		}
		return;
	}
	void add(int a,int d,int id){
		for(int i = H-1;i>=0;i--){
			if(d&(1<<i)){
				add_edge(stree[a][i],id);
				add_edge(id,etree[a][i]);
				a = par[a][i];
			}
		}
		return;
	}
	int LCA(int a,int b){
		if(dep[a]<dep[b])swap(a,b);
		int d = dep[a]-dep[b];
		for(int i = H-1;i>=0;i--){
			if(d&(1<<i))a = par[a][i];
		}
		for(int i = H-1;i>=0;i--){
			if(par[a][i] != par[b][i])a = par[a][i],b = par[b][i];
		}
		return (a==b?a:par[a][0]);
	}
	void GO(){
		par[1][0] = 1;
		dfs(1);
	}
	void ADD_CON(){
		for(int i = 1;i<=M;i++){
			int a = arr[i].fs,b = arr[i].sc;
			int p = LCA(a,b);
			add(a,dep[a]-dep[p],i);
			add(b,dep[b]-dep[p],i);
			add_edge(sleaf[a],i);
			add_edge(i,sleaf[a]);
			add_edge(eleaf[b],i);
			add_edge(i,eleaf[b]);
			/*
			cerr<<"ADD:"<<endl;
			cerr<<i<<":"<<a<<' '<<b<<' '<<sleaf[a]<<','<<eleaf[b]<<endl;

		   */
		}
		return;
	}
	void PRINT(){
		for(int i = 1;i<=vcnt;i++){
			cout<<i<<":";
			for(int eid = head[i];eid;eid = nid[eid]){
				cout<<to[eid]<<',';
			}cout<<endl;
		}
	}
	void init(){
		dep[1] = 0;
		for(int i = 0;i<=vcnt;i++)head[i] = 0;
	}
}

namespace SCC{
	int deg[mxn*100],low[mxn*100],idx[mxn*100],gid[mxn*100],cnt,gcnt;
	int dp[mxn*100];
	vector<int> st;
	void dfs(int now){
		idx[now] = low[now] = ++cnt;
		st.push_back(now);
		for(int eid = head[now];eid;eid = nid[eid]){
			int nxt = to[eid];
			if(gid[nxt])continue;
			if(!idx[nxt]){
				dfs(nxt);
				low[now] = min(low[now],low[nxt]);
			}
			else low[now] = min(low[now],idx[nxt]);
		}
		if(idx[now] == low[now]){
			gcnt++;
			while(st.back() != now){
				gid[st.back()] = gcnt;
				st.pop_back();
			}
			gid[st.back()] = gcnt;
			st.pop_back();
		}
		return;
	}
	void GO(){
		for(int i = 1;i<=vcnt;i++){
			if(!idx[i])dfs(i);
		}
		for(int i = 1;i<=M;i++){
			dp[gid[i]]++;
		}
		if(*max_element(dp,dp+gcnt+1)>1){
			cout<<"No\n";
			return;
		}
		else cout<<"Yes\n";
		return;
	}
	void init(){
		for(int i = 1;i<=vcnt;i++){
			gid[i] = dp[i] = idx[i] = low[i] = 0;
		}
		gcnt = cnt = 0;
		return;
	}
}

void init(){
	for(int i = 0;i<=N;i++){
		tree[i].clear();
	}
	SCC::init();
	BUILD::init();
	vcnt = ecnt = 0;
	return;
}

void solve(){
	init();
	cin>>N;
	for(int i = 1;i<N;i++){
		int a,b;
		cin>>a>>b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	cin>>M;
	for(int i = 1;i<=M;i++){
		cin>>arr[i].fs>>arr[i].sc;
	}
	vcnt = M;
	BUILD::GO();
	BUILD::ADD_CON();
	//BUILD::PRINT();
	SCC::GO();
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t;cin>>t;
	while(t--)solve();
}

• 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