oj.uz

Submission #695269

# Submission time Handle Problem Language Result Execution time Memory
695269 2023-02-04T20:54:55 Z Ahmed_Solyman Railway (BOI17_railway) C++14
8 / 100
 1000 ms 30752 KB 
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m,k;
	cin>>n>>m>>k;
	vector<int>adj[n+5];
	vector<int>a(n+5),b(n+5);
	for(int i=0;i<n-1;i++){
		int u,v;cin>>u>>v;
		a[i]=u;b[i]=v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	vector<int>vis(n+5);
	map<pair<int,int>,int>e;
	vector<int>parent(n+5);
	while(m--){
		int k;cin>>k;
		vector<int>v(k);
		for(auto &i:v)cin>>i;
		int root=v[0];
		queue<int>q;
		q.push(root);
		for(int i=0;i<n;i++)vis[i+1]=0,parent[i+1]=0;
		while(q.size()){
			int x=q.front();
			q.pop();
			vis[x]=1;
			for(auto i:adj[x]){
				if(!vis[i]){
					q.push(i);
					parent[i]=x;
				}
			}
		}
		map<pair<int,int>,bool>z;
		for(int i=1;i<k;i++){
			int u=v[i];
			while(u!=root){
				z[{u,parent[u]}]=1;
				z[{parent[u],u}]=1;
				u=parent[u];
			}
		}
		for(auto i:z){
			//cout<<i.first.first<<" : "<<i.first.second<<endl;
			e[i.first]++;
		}
	}
	vector<int>d;
	for(int i=0;i<n-1;i++){
		if(e[{a[i],b[i]}]>=k){
			d.push_back(i+1);
		}
	}
	cout<<d.size()<<endl;
	for(auto i:d)cout<<i<<" ";
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 58 ms 1732 KB Output is correct
3 Correct 59 ms 1704 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 573 ms 2476 KB Output is correct
7 Correct 76 ms 1868 KB Output is correct
8 Correct 129 ms 1868 KB Output is correct
9 Correct 140 ms 1768 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 304 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 58 ms 1732 KB Output is correct
3 Correct 59 ms 1704 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 573 ms 2476 KB Output is correct
7 Correct 76 ms 1868 KB Output is correct
8 Correct 129 ms 1868 KB Output is correct
9 Correct 140 ms 1768 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 304 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 547 ms 2428 KB Output is correct
16 Correct 532 ms 2328 KB Output is correct
17 Correct 513 ms 2476 KB Output is correct
18 Execution timed out 1089 ms 1928 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 30752 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 17604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 17604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 58 ms 1732 KB Output is correct
3 Correct 59 ms 1704 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 573 ms 2476 KB Output is correct
7 Correct 76 ms 1868 KB Output is correct
8 Correct 129 ms 1868 KB Output is correct
9 Correct 140 ms 1768 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 304 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 547 ms 2428 KB Output is correct
16 Correct 532 ms 2328 KB Output is correct
17 Correct 513 ms 2476 KB Output is correct
18 Execution timed out 1089 ms 1928 KB Time limit exceeded
19 Halted 0 ms 0 KB -