Submission #551821

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
551821	2022-04-21T16:21:09 Z	kshitij_sodani	Jail (JOI22_jail)	C++14	21 / 100	5000 ms	5204 KB

jail

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
#define endl '\n'
const llo mod=1e9+7;

int q;
int ee;
vector<int> adj[200001];
int cc[200001];
int dd[200001];
int vis[200001];
vector<int> ss;
vector<int> tt;
vector<int> pre[501];
map<int,int> ind[501];
void dfs(int no,int par=-1){
	ss.pb(no);
	if(ee==no){
		tt=ss;

	}
	for(auto j:adj[no]){
		if(j!=par){
			dfs(j,no);
		}
	}
	ss.pop_back();
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>q;
	while(q--){
		int n;
		cin>>n;
		for(int i=0;i<n;i++){
			adj[i].clear();

		}
		for(int i=0;i<n-1;i++){
			int aa,bb;
			cin>>aa>>bb;
			aa--;
			bb--;
			adj[aa].pb(bb);
			adj[bb].pb(aa);
		}
		int m;
		cin>>m;
		for(int i=0;i<m;i++){
			cin>>cc[i]>>dd[i];
			ind[i].clear();
			cc[i]--;
			dd[i]--;
			ee=dd[i];
			dfs(cc[i]);
			pre[i]=tt;
			for(auto j:tt){
				ind[i][j]++;
			}
		}

		string ans="No";
		vector<int> ss;
		for(int i=0;i<m;i++){
			ss.pb(i);
		}
		while(true){
			for(int j=0;j<n;j++){
				vis[j]=0;
			}
			for(int j=0;j<m;j++){
				vis[cc[j]]=1;
			}
			int ok=0;
			for(auto j:ss){
				vis[cc[j]]=0;
				for(auto i:pre[j]){
					if(vis[i]==1){
						ok++;
					}
				}
				vis[dd[j]]=1;
			}
			if(ok==0){
				ans="Yes";
			}

			if(next_permutation(ss.begin(),ss.end())){

			}
			else{
				break;
			}
		}
		cout<<ans<<endl;
		/*for(int i=0;i<m;i++){
			for(int j=0;j<m;j++){
				int co=0;
				if(i==j){
					continue;
				}
				if(ind[j].find(cc[i])!=ind[j].end()){
					if(ind[j].find(dd[i])!=ind[j].end()){
						ans="No";
					}
				}
				for(auto jj:pre[j]){
					if(ind[i].find(dd[j]))
				}
				if(ind[j].find(dd[i])!=ind[j].end()){
					if(ind[i].find(pre[j].back())!=ind[i].end()){
						ans="No";
						break;
					}
				}
			}
		}*/
	//	cout<<ans<<endl;
	}






	return 0;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	3 ms	4948 KB	Output is correct
4	Correct	16 ms	5160 KB	Output is correct
5	Correct	29 ms	5100 KB	Output is correct
6	Correct	4 ms	5072 KB	Output is correct
7	Correct	12 ms	5108 KB	Output is correct
8	Execution timed out	5053 ms	5076 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5076 KB	Output is correct
2	Correct	4 ms	5052 KB	Output is correct
3	Correct	4 ms	5072 KB	Output is correct
4	Correct	4 ms	5064 KB	Output is correct
5	Correct	4 ms	5076 KB	Output is correct
6	Correct	4 ms	5032 KB	Output is correct
7	Correct	4 ms	5076 KB	Output is correct
8	Correct	4 ms	5076 KB	Output is correct
9	Correct	4 ms	5116 KB	Output is correct
10	Correct	4 ms	5076 KB	Output is correct
11	Correct	4 ms	5076 KB	Output is correct
12	Correct	4 ms	5068 KB	Output is correct
13	Correct	4 ms	5036 KB	Output is correct

Subtask #3
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5076 KB	Output is correct
2	Correct	4 ms	5052 KB	Output is correct
3	Correct	4 ms	5072 KB	Output is correct
4	Correct	4 ms	5064 KB	Output is correct
5	Correct	4 ms	5076 KB	Output is correct
6	Correct	4 ms	5032 KB	Output is correct
7	Correct	4 ms	5076 KB	Output is correct
8	Correct	4 ms	5076 KB	Output is correct
9	Correct	4 ms	5116 KB	Output is correct
10	Correct	4 ms	5076 KB	Output is correct
11	Correct	4 ms	5076 KB	Output is correct
12	Correct	4 ms	5068 KB	Output is correct
13	Correct	4 ms	5036 KB	Output is correct
14	Correct	3 ms	5076 KB	Output is correct
15	Correct	3 ms	5076 KB	Output is correct
16	Correct	14 ms	5192 KB	Output is correct
17	Correct	5 ms	5076 KB	Output is correct
18	Correct	11 ms	5068 KB	Output is correct
19	Correct	3 ms	4948 KB	Output is correct
20	Correct	9 ms	5064 KB	Output is correct
21	Correct	7 ms	5076 KB	Output is correct
22	Correct	9 ms	5076 KB	Output is correct
23	Correct	5 ms	4948 KB	Output is correct
24	Correct	4 ms	5076 KB	Output is correct
25	Correct	13 ms	5076 KB	Output is correct
26	Correct	6 ms	5076 KB	Output is correct
27	Correct	6 ms	5076 KB	Output is correct
28	Correct	5 ms	5080 KB	Output is correct

Subtask #4
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5076 KB	Output is correct
2	Correct	4 ms	5052 KB	Output is correct
3	Correct	4 ms	5072 KB	Output is correct
4	Correct	4 ms	5064 KB	Output is correct
5	Correct	4 ms	5076 KB	Output is correct
6	Correct	4 ms	5032 KB	Output is correct
7	Correct	4 ms	5076 KB	Output is correct
8	Correct	4 ms	5076 KB	Output is correct
9	Correct	4 ms	5116 KB	Output is correct
10	Correct	4 ms	5076 KB	Output is correct
11	Correct	4 ms	5076 KB	Output is correct
12	Correct	4 ms	5068 KB	Output is correct
13	Correct	4 ms	5036 KB	Output is correct
14	Correct	3 ms	5076 KB	Output is correct
15	Correct	3 ms	5076 KB	Output is correct
16	Correct	14 ms	5192 KB	Output is correct
17	Correct	5 ms	5076 KB	Output is correct
18	Correct	11 ms	5068 KB	Output is correct
19	Correct	3 ms	4948 KB	Output is correct
20	Correct	9 ms	5064 KB	Output is correct
21	Correct	7 ms	5076 KB	Output is correct
22	Correct	9 ms	5076 KB	Output is correct
23	Correct	5 ms	4948 KB	Output is correct
24	Correct	4 ms	5076 KB	Output is correct
25	Correct	13 ms	5076 KB	Output is correct
26	Correct	6 ms	5076 KB	Output is correct
27	Correct	6 ms	5076 KB	Output is correct
28	Correct	5 ms	5080 KB	Output is correct
29	Execution timed out	5057 ms	5072 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-

Subtask #5
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5076 KB	Output is correct
2	Correct	4 ms	5052 KB	Output is correct
3	Correct	4 ms	5072 KB	Output is correct
4	Correct	4 ms	5064 KB	Output is correct
5	Correct	4 ms	5076 KB	Output is correct
6	Correct	4 ms	5032 KB	Output is correct
7	Correct	4 ms	5076 KB	Output is correct
8	Correct	4 ms	5076 KB	Output is correct
9	Correct	4 ms	5116 KB	Output is correct
10	Correct	4 ms	5076 KB	Output is correct
11	Correct	4 ms	5076 KB	Output is correct
12	Correct	4 ms	5068 KB	Output is correct
13	Correct	4 ms	5036 KB	Output is correct
14	Correct	3 ms	5076 KB	Output is correct
15	Correct	3 ms	5076 KB	Output is correct
16	Correct	14 ms	5192 KB	Output is correct
17	Correct	5 ms	5076 KB	Output is correct
18	Correct	11 ms	5068 KB	Output is correct
19	Correct	3 ms	4948 KB	Output is correct
20	Correct	9 ms	5064 KB	Output is correct
21	Correct	7 ms	5076 KB	Output is correct
22	Correct	9 ms	5076 KB	Output is correct
23	Correct	5 ms	4948 KB	Output is correct
24	Correct	4 ms	5076 KB	Output is correct
25	Correct	13 ms	5076 KB	Output is correct
26	Correct	6 ms	5076 KB	Output is correct
27	Correct	6 ms	5076 KB	Output is correct
28	Correct	5 ms	5080 KB	Output is correct
29	Execution timed out	5057 ms	5072 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-

Subtask #6
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	3 ms	5076 KB	Output is correct
3	Correct	2 ms	4948 KB	Output is correct
4	Correct	3 ms	4948 KB	Output is correct
5	Execution timed out	5063 ms	5204 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #7
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	3 ms	4948 KB	Output is correct
4	Correct	16 ms	5160 KB	Output is correct
5	Correct	29 ms	5100 KB	Output is correct
6	Correct	4 ms	5072 KB	Output is correct
7	Correct	12 ms	5108 KB	Output is correct
8	Execution timed out	5053 ms	5076 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

Submission #551821

Compilation message

Subtask #1 0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 16.0 / 16.0

Subtask #4 0 / 28.0

Subtask #5 0 / 12.0

Subtask #6 0 / 11.0

Subtask #7 0 / 23.0

Subtask #1
0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
16.0 / 16.0

Subtask #4
0 / 28.0

Subtask #5
0 / 12.0

Subtask #6
0 / 11.0

Subtask #7
0 / 23.0