Submission #1181075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181075		LCJLY	Jail (JOI22_jail)	C++20	100 / 100	932 ms	126144 KiB

jail

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

#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

vector<int>adj[120005];

int d[120005];
int sz[120005];
int pp[120005];
int hp[120005];

void dfs(int index, int par){
	if(adj[index].size()>2&&adj[index][0]==par) swap(adj[index][0],adj[index][1]);
	sz[index]=1;
	for(auto &it:adj[index]){
		if(it==par) continue;
		d[it]=d[index]+1;
		dfs(it,index);
		sz[index]+=sz[it];
		pp[it]=index;
		if(sz[it]>sz[adj[index][0]]) swap(it,adj[index][0]);
	}
}

int in[120005];
int out[120005];
int ptr=0;

void hld(int index, int par){
	in[index]=++ptr;
	for(auto it:adj[index]){
		if(it==par) continue;
		if(it==adj[index][0]) hp[it]=hp[index];
		else hp[it]=it;
		hld(it,index);
	}
	out[index]=ptr;
}


vector<int>adj2[700005];


struct node{
	int s,e,m;
	node *l,*r;
	int v;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1){
		v=ptr;
		ptr+=2;
		// show3(s,s,e,e,v,v);
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
			adj2[v].push_back(l->v);
			adj2[v].push_back(r->v);
			adj2[l->v+1].push_back(v+1);
			adj2[r->v+1].push_back(v+1);
		}
	}
	
	void upd(int x, int y, int c, int amos){
		if(x>y) return;
		if(x<=s&&y>=e){
			if(amos==0) adj2[c].push_back(v); //go down
			else if(amos==1) adj2[v+1].push_back(c); //go up
			else if(amos==2) adj2[c].push_back(v+1);
			else adj2[v].push_back(c);
			return;
		}
		if(x<=m) l->upd(x,y,c,amos);
		if(y>m) r->upd(x,y,c,amos);
	}
};

bool visited[700005];
bool visited2[700005];
bool cycle=false;

void dfs2(int index, int par){
	visited[index]=true;
	visited2[index]=true;
	for(auto it:adj2[index]){	
		if(visited2[it]) cycle=true;
		else if(!visited[it]){
			dfs2(it,index);
		}
	}
	visited2[index]=false;
}

void solve(){
	int n;
	cin >> n;
	
	//reset
	for(int x=0;x<=n;x++){
		adj[x].clear();
		hp[x]=0;
		in[x]=0;
		out[x]=0;
		sz[x]=0;
		pp[x]=0;
	}
	ptr=0;

	int temp,temp2;
	for(int x=0;x<n-1;x++){
		cin >> temp >> temp2;
		adj[temp].push_back(temp2);
		adj[temp2].push_back(temp);
	}
	
	hp[1]=1;
	dfs(1,-1);
	hld(1,-1);
	
	int m;
	cin >> m;
	
	//reset
	for(int x=0;x<=m+n*4+10;x++){
		adj2[x].clear();
		visited[x]=0;
		visited2[x]=0;
	}
	
	pii arr[m];
	for(int x=0;x<m;x++){
		cin >> arr[x].first >> arr[x].second;
	}
	
	ptr=m;
	node st(0,n);
	
	for(int x=0;x<m;x++){
		int a=arr[x].first;
		int b=arr[x].second;
		
		st.upd(in[b],in[b],x,3);
		st.upd(in[a],in[a],x,2);

		while(hp[a]!=hp[b]){
			if(d[hp[a]]<d[hp[b]]) swap(a,b);
			//so a is always deeper
			if(in[hp[a]]<=in[arr[x].second]&&in[a]>=in[arr[x].second]){
				st.upd(in[hp[a]],in[arr[x].second]-1,x,0);
				st.upd(in[arr[x].second]+1,in[a],x,0);
			}
			else st.upd(in[hp[a]],in[a],x,0);

			if(in[hp[a]]<=in[arr[x].first]&&in[a]>=in[arr[x].first]){
				st.upd(in[hp[a]],in[arr[x].first]-1,x,1);
				st.upd(in[arr[x].first]+1,in[a],x,1);
			}
			else st.upd(in[hp[a]],in[a],x,1);


			a=pp[hp[a]];
		}

		if(in[a]>in[b]) swap(a,b);

		if(in[a]<=in[arr[x].second]&&in[b]>=in[arr[x].second]){
			st.upd(in[a],in[arr[x].second]-1,x,0);
			st.upd(in[arr[x].second]+1,in[b],x,0);
		}
		else st.upd(in[a],in[b],x,0);

		if(in[a]<=in[arr[x].first]&&in[b]>=in[arr[x].first]){
			st.upd(in[a],in[arr[x].first]-1,x,1);
			st.upd(in[arr[x].first]+1,in[b],x,1);
		}
		else st.upd(in[a],in[b],x,1);
	}
	
	cycle=false;
	//cycle checking
	for(int x=0;x<m;x++){
		if(visited[x]) continue;
		dfs2(x,-1);
	}

	if(cycle) cout << "No\n";
	else cout << "Yes\n";
	
}
																   
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	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