oj.uz

Submission #635243

# Submission time Handle Problem Language Result Execution time Memory
635243 2022-08-25T17:41:28 Z alvingogo Jail (JOI22_jail) C++14
0 / 100
 885 ms 284620 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){
		if(x<0 || y<0){
			return;
		}
		//cout << x << " " << y << "\n";
		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;
	}
};
const int all=18;
struct no{
	vector<int> ch;
	int dep=-1;
	int fa=-1;
	int as[all]={0};
};
vector<no> v;
void dfs(int r,int f){
	v[r].dep=v[f].dep+1;
	v[r].as[0]=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<pair<int,int> > g;
		vector<int> s(n,-1),t(n,-1);
		TOPO tp;
		tp.init(m+2*all*n+2*n);
		for(int i=0;i<m;i++){
			int a,b;
			cin >> a >> b;
			a--;
			b--;
			s[a]=i;
			tp.add(i,m+all*2*n+a);
			t[b]=i;
			tp.add(m+all*2*n+n+b,i);
			g.push_back({a,b});
		}
		for(int i=0;i<n;i++){
			tp.add(m+all*2*n+i,m+all*i);
			tp.add(m+all*2*n+v[i].as[0],m+all*i);
			tp.add(m+all*n+all*i,m+all*2*n+n+i);
			tp.add(m+all*n+all*i,m+all*2*n+n+v[i].as[0]);
		}
		for(int i=1;i<all;i++){
			for(int j=0;j<n;j++){
				v[j].as[i]=v[v[j].as[i-1]].as[i-1];
				tp.add(m+all*j+i-1,m+all*j+i);
				tp.add(m+all*v[j].as[i-1]+i-1,m+all*j+i);
				tp.add(m+all*n+all*j+i,m+all*n+all*j+i-1);
				tp.add(m+all*n+all*j+i,m+all*n+all*v[j].as[i-1]+i-1);
			}
		}
		auto query=[&](int r,int f,int cnt){
			for(int i=all-1;i>=0;i--){
				if(v[v[r].as[i]].dep>v[f].dep){
					tp.add(m+all*r+i,cnt);
					tp.add(cnt,m+all*n+all*r+i);
					r=v[r].as[i];
				}
			}
		};
		int cnt=0;
		for(auto h:g){
			int a=h.fs,b=h.sc;
			int lca;
			if(v[a].dep>v[b].dep){
				for(int i=all-1;i>=0;i--){
					if(v[v[a].as[i]].dep>=v[b].dep){
						a=v[a].as[i];
					}
				}
			}
			else if(v[b].dep>v[a].dep){
				for(int i=all-1;i>=0;i--){
					if(v[v[b].as[i]].dep>=v[a].dep){
						b=v[b].as[i];
					}
				}
			}
			if(a==b){
				lca=a;
			}
			else{
				for(int i=all-1;i>=0;i--){
					if(v[b].as[i]!=v[a].as[i]){
						a=v[a].as[i];
						b=v[b].as[i];
					}
				}
				lca=v[a].as[0];
			}
			a=h.fs;
			b=h.sc;
			tp.add(cnt,t[a]);
			tp.add(s[b],cnt);
			if(lca==a){
				b=v[b].as[0];
				query(b,a,cnt);
			}
			else if(lca==b){
				a=v[a].as[0];
				query(a,b,cnt);
			}
			else{
				a=v[a].as[0];
				b=v[b].as[0];
				query(a,lca,cnt);
				query(b,lca,cnt);
				tp.add(cnt,t[lca]);
				tp.add(s[lca],cnt);
			}
			cnt++;
		}
		if(tp.solve()){
			cout << "Yes\n";
		}
		else{
			cout << "No\n";
		}
	}
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 194 ms 596 KB Output is correct
5 Correct 411 ms 596 KB Output is correct
6 Correct 18 ms 932 KB Output is correct
7 Correct 21 ms 932 KB Output is correct
8 Correct 20 ms 940 KB Output is correct
9 Correct 608 ms 14864 KB Output is correct
10 Correct 885 ms 284620 KB Output is correct
11 Incorrect 82 ms 412 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 19 ms 884 KB Output is correct
4 Correct 19 ms 928 KB Output is correct
5 Correct 19 ms 928 KB Output is correct
6 Correct 19 ms 928 KB Output is correct
7 Correct 19 ms 884 KB Output is correct
8 Correct 21 ms 884 KB Output is correct
9 Correct 20 ms 884 KB Output is correct
10 Correct 19 ms 884 KB Output is correct
11 Correct 16 ms 964 KB Output is correct
12 Correct 10 ms 876 KB Output is correct
13 Incorrect 10 ms 884 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 19 ms 884 KB Output is correct
4 Correct 19 ms 928 KB Output is correct
5 Correct 19 ms 928 KB Output is correct
6 Correct 19 ms 928 KB Output is correct
7 Correct 19 ms 884 KB Output is correct
8 Correct 21 ms 884 KB Output is correct
9 Correct 20 ms 884 KB Output is correct
10 Correct 19 ms 884 KB Output is correct
11 Correct 16 ms 964 KB Output is correct
12 Correct 10 ms 876 KB Output is correct
13 Incorrect 10 ms 884 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 19 ms 884 KB Output is correct
4 Correct 19 ms 928 KB Output is correct
5 Correct 19 ms 928 KB Output is correct
6 Correct 19 ms 928 KB Output is correct
7 Correct 19 ms 884 KB Output is correct
8 Correct 21 ms 884 KB Output is correct
9 Correct 20 ms 884 KB Output is correct
10 Correct 19 ms 884 KB Output is correct
11 Correct 16 ms 964 KB Output is correct
12 Correct 10 ms 876 KB Output is correct
13 Incorrect 10 ms 884 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 19 ms 884 KB Output is correct
4 Correct 19 ms 928 KB Output is correct
5 Correct 19 ms 928 KB Output is correct
6 Correct 19 ms 928 KB Output is correct
7 Correct 19 ms 884 KB Output is correct
8 Correct 21 ms 884 KB Output is correct
9 Correct 20 ms 884 KB Output is correct
10 Correct 19 ms 884 KB Output is correct
11 Correct 16 ms 964 KB Output is correct
12 Correct 10 ms 876 KB Output is correct
13 Incorrect 10 ms 884 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 97 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 194 ms 596 KB Output is correct
5 Correct 411 ms 596 KB Output is correct
6 Correct 18 ms 932 KB Output is correct
7 Correct 21 ms 932 KB Output is correct
8 Correct 20 ms 940 KB Output is correct
9 Correct 608 ms 14864 KB Output is correct
10 Correct 885 ms 284620 KB Output is correct
11 Incorrect 82 ms 412 KB Output isn't correct
12 Halted 0 ms 0 KB -