oj.uz

답안 #631591

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
631591 2022-08-18T09:29:31 Z alvingogo Jail (JOI22_jail) C++14
0 / 100
 1 ms 240 KB 
#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){
				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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 240 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -