Submission #952106

#	Time	Username	Problem	Language	Result	Execution time	Memory
952106		ting39	Jail (JOI22_jail)	C++17	49 / 100	959 ms	1048576 KiB

jail

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
vector<vector<int>> g,ng;
vector<int> s,t,dep,jump[18],in,out;
int tme=0;
struct BIT{
	int n,m;
	vector<vector<int>> b;
	BIT(int _n,int _m):n(_n),m(_m){
		b.resize(n+1,vector<int>(m));
	}
	void add(int x,int k,int val){
		for(int i=x;i<=n;i+=i&-i){
			b[i][k]+=val;
		}
	}
	vector<int> qry(int x){
		vector<int> ret(m);
		for(int i=x;i>0;i-=i&-i){
			for(int j=0;j<m;j++){
				ret[j]+=b[i][j];
			}
		}
		return ret;
	}
};
void dfs(int pre,int pos){
	in[pos]=tme;
	tme++;
	for(int i:g[pos]){
		if(i==pre) continue;
		dep[i]=dep[pos]+1;
		jump[0][i]=pos;
		dfs(pos,i);
	}
	out[pos]=tme;
	tme++;
}
int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	int dif=dep[x]-dep[y],cnt=0;//cout<<x<<' '<<y<<' '<<dif<<endl;
	while(dif){
		if(dif&1) x=jump[cnt][x];
		cnt++;
		dif>>=1;
	}//cout<<x<<' '<<y<<endl;
	if(x==y) return x;
	for(int i=17;i>=0;i--){
		if(jump[i][x]!=jump[i][y]){
			x=jump[i][x];
			y=jump[i][y];
		}//cout<<x<<' '<<y<<endl;
	}
	return jump[0][x];
}
vector<int> merge(vector<int> x,vector<int> y,int c){//cout<<"ok"<<endl;
	//for(int i:x) cout<<i<<' ';cout<<endl;for(int i:y) cout<<i<<' ';cout<<endl;
	for(int i=0;i<x.size();i++){
		x[i]+=y[i]*c;
	}
	//for(int i:x) cout<<i<<' ';cout<<endl;
	return x;
}
vector<int> search(int x,int y,BIT *Bit){
	vector<int> ret;
	int LCA=lca(x,y);//cout<<LCA<<endl;
	ret=merge(Bit->qry(in[x]+1),Bit->qry(in[y]+1),1);
	ret=merge(ret,Bit->qry(in[LCA]+1),-1);
	ret=merge(ret,Bit->qry(in[LCA]),-1);//for(int i:ret) cout<<i<<' ';cout<<endl;
	return ret;
}
void insert(int p,int x,BIT *Bit){
	Bit->add(in[p]+1,x,1);
	Bit->add(out[p]+1,x,-1);
}
signed main(){
	int tt;
	cin>>tt;
	while(tt--){
		tme=0;
		int n;
		cin>>n;
		g.clear();
		ng.clear();
		for(auto &i:jump){
			i.resize(n,0);
		}
		dep.resize(n,0);
		g.resize(n);
		in.resize(n);
		out.resize(n);
		for(int i=0;i<n-1;i++){
			int a,b;
			cin>>a>>b;
			a--;
			b--;
			g[a].push_back(b);
			g[b].push_back(a);
		}
		int m;
		cin>>m;
		ng.resize(m);
		s.resize(m);
		t.resize(m);
		dfs(0,0);
		for(int i=1;i<18;i++){
			for(int j=0;j<n;j++){
				jump[i][j]=jump[i-1][jump[i-1][j]];
			}
		}
		BIT bits1(n*2,m),bitt1(n*2,m),bits2(n*2,m),bitt2(n*2,m);
		for(int i=0;i<m;i++){
			cin>>s[i]>>t[i];
			s[i]--;
			t[i]--;//cout<<s[i]<<' '<<t[i]<<endl;
		}
		vector<int> du(m);
		for(int i=0;i<m;i++){
			vector<int> tmp1=search(s[i],t[i],&bits1),tmp2=search(s[i],t[i],&bitt1);
			//for(int j:tmp1) cout<<j<<' ';cout<<endl;
			for(int j=0;j<m;j++){
				if(tmp1[j]){
					ng[i].push_back(j);
					du[j]++;
					//cout<<i<<' '<<j<<endl;
				}
				if(tmp2[j]){
					ng[j].push_back(i);
					du[i]++;
					//cout<<j<<' '<<i<<endl;
				}
			}
			insert(s[i],i,&bits1);
			insert(t[i],i,&bitt1);
		}
		for(int i=m-1;i>=0;i--){
			vector<int> tmp1=search(s[i],t[i],&bits2),tmp2=search(s[i],t[i],&bitt2);
			//for(int j:tmp1) cout<<j<<' ';cout<<endl;
			for(int j=0;j<m;j++){
				if(tmp1[j]){
					ng[i].push_back(j);
					du[j]++;
					//cout<<i<<' '<<j<<endl;
				}
				if(tmp2[j]){
					ng[j].push_back(i);
					du[i]++;
					//cout<<j<<' '<<i<<endl;
				}
			}
			insert(s[i],i,&bits2);
			insert(t[i],i,&bitt2);
		}
		queue<int> q;
		for(int i=0;i<m;i++){
			if(!du[i]) q.push(i);
		}
		while(!q.empty()){
			int pos=q.front();
			q.pop();
			for(int i:ng[pos]){
				du[i]--;
				if(!du[i]) q.push(i);
			}
		}
		int ans=1;
		for(int i=0;i<m;i++){
			if(du[i]) ans=0;
		}
		if(ans) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
}

Compilation message (stderr)

jail.cpp: In function 'std::vector<long long int> merge(std::vector<long long int>, std::vector<long long int>, long long int)':
jail.cpp:62:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int i=0;i<x.size();i++){
      |              ~^~~~~~~~~

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