Submission #631593

#	Time	Username	Problem	Language	Result	Execution time	Memory
631593		alvingogo	Jail (JOI22_jail)	C++14	72 / 100	3264 ms	1048576 KiB

jail

#include <bits/stdc++.h>
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define cd complex<double>
#define p_q priority_queue
using namespace std;

struct TOPO{
	vector<vector<int> > e;
	int n;
	vector<int> in;
	void init(int x){
		e.resize(x);
		in.resize(x);
		n=x;
	}
	void add(int x,int y){
		e[x].push_back(y);
		in[y]++;
	}
	bool solve(){
		int cnt=0;
		queue<int> q;
		for(int i=0;i<n;i++){
			if(in[i]==0){
				q.push(i);
			}
		}
		while(q.size()){
			int a=q.front();
			q.pop();
			cnt++;
			for(auto h:e[a]){
				in[h]--;
				if(in[h]==0){
					q.push(h);
				}
			}
		}
		return cnt==n;
	}
};
struct no{
	vector<int> ch;
	int dep=-1;
	int fa=-1;
	vector<int> s,t;
};
vector<no> v;
void dfs(int r,int f){
	v[r].dep=v[f].dep+1;
	v[r].fa=f;
	for(auto h:v[r].ch){
		if(h!=f){
			dfs(h,r);
		}
	}
}
int main(){
	AquA;
	int q;
	cin >> q;
	while(q--){
		int n;
		cin >> n;
		v.clear();
		v.resize(n);
		for(int i=1;i<n;i++){
			int a,b;
			cin >> a >> b;
			a--;
			b--;
			v[a].ch.push_back(b);
			v[b].ch.push_back(a);
		}
		dfs(0,0);
		int m;
		cin >> m;
		vector<vector<int> > f(m);
		vector<pair<int,int> > t;
		for(int i=0;i<m;i++){
			int a,b;
			cin >> a >> b;
			a--;
			b--;
			v[a].s.push_back(i);
			v[b].t.push_back(i);
			vector<int> c,d;
			while(v[a].dep>v[b].dep){
				c.push_back(a);
				a=v[a].fa;
			}
			while(v[b].dep>v[a].dep){
				d.push_back(b);
				b=v[b].fa;
			}
			if(a==b){
				c.push_back(a);
				for(auto h:c){
					f[i].push_back(h);
				}
				reverse(d.begin(),d.end());
				for(auto h:d){
					f[i].push_back(h);
				}
				continue;
			}
			while(a!=b){
				c.push_back(a);
				d.push_back(b);
				a=v[a].fa;
				b=v[b].fa;
			}
			c.push_back(a);
			for(auto h:c){
				f[i].push_back(h);
			}
			reverse(d.begin(),d.end());
			for(auto h:d){
				f[i].push_back(h);
			}
		}	
		TOPO tp;
		tp.init(m);
		for(int i=0;i<m;i++){
			auto h=f[i];
			for(auto y:h){
				for(auto z:v[y].s){
					if(z!=i){
						tp.add(z,i);
					}
				}
				for(auto z:v[y].t){
					if(z!=i){
						tp.add(i,z);
					}
				}
			}
		}
		if(tp.solve()){
			cout << "Yes\n";
		}
		else{
			cout << "No\n";
		}
	}
	return 0;
}

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