# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
282027 |
2020-08-23T20:04:38 Z |
JoMee |
Railway (BOI17_railway) |
C++17 |
|
1000 ms |
65400 KB |
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define rep(i,a,n) for(int i = a; i<n; i++)
#define per(i,a,n) for(int i = n-1; i>=a; i--)
int max(int a,int b){return (a>b)?a:b;}
int min(int a,int b){return (a<b)?a:b;}
vector<int> adj[100005];
int par[20][100005], szs[100005], depth[100005];
set<int> start[100005];
set<int> out[100005];
pair<int,int> edges[100005];
void dfs(int e,int p){
par[0][e] = p;
depth[e] = depth[p]+1;
for(int j:adj[e]){
if(j != p)dfs(j,e);
}
}
set<int>* smldfs(int i,int p){
set<int>* ret = new set<int>(start[i].begin(),start[i].end());
for(auto e:adj[i]){
if(e != p){
set<int>* v = smldfs(e,i);
if(v->size() > ret->size())swap(v,ret);
for(auto f:(*v)){
ret->insert(f);
}
}
}
for(auto f:out[i]){
ret->erase(f);
}
szs[i] = ret->size();
return ret;
}
int moveUp(int idx,int d){
for(int i = 0; i<=20; i++){
if(d&(1<<i))idx = par[i][idx];
}
return idx;
}
int lca(int a,int b){
if(depth[a] < depth[b])swap(a,b);
a = moveUp(a,depth[a]-depth[b]);
if(a == b)return a;
for(int i = 20; i >= 0; i++){
if(par[i][a] != par[i][b]){
a = par[i][a];
b = par[i][b];
}
}
return par[0][a];
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,k,m;
cin>>n>>m>>k;
rep(i,0,n-1){
int a,b;
cin>>a>>b;a--;b--;
adj[a].push_back(b);
adj[b].push_back(a);
edges[i] = make_pair(a,b);
}
memset(szs,0,sizeof(szs));
depth[0] = -1;
dfs(0,0);
rep(i,1,20)rep(j,0,100005)par[i][j] = par[i-1][par[i-1][j]];
rep(i,0,m){
int x;
cin>>x;
int la = -1;
rep(j,0,x){
int k;
cin>>k;k--;
start[k].insert(i);
if(la == -1)la = k;
else{
la = lca(la,k);
}
}
out[la].insert(i);
}
smldfs(0,0);
vector<int> ans;
rep(i,0,n-1){
int a = (depth[edges[i].first] > depth[edges[i].second])?edges[i].first:edges[i].second;
if(szs[a] >= k)ans.push_back(i+1);
}
cout<<ans.size()<<"\n";
for(auto i:ans)cout<<i<<" ";
cout<<"\n";
}
Compilation message
railway.cpp: In function 'long long int lca(long long int, long long int)':
railway.cpp:57:5: warning: iteration 9223372036854775787 invokes undefined behavior [-Waggressive-loop-optimizations]
57 | for(int i = 20; i >= 0; i++){
| ^~~
railway.cpp:57:23: note: within this loop
57 | for(int i = 20; i >= 0; i++){
| ~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1085 ms |
27776 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1085 ms |
27776 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
240 ms |
63436 KB |
Output is correct |
2 |
Correct |
18 ms |
27776 KB |
Output is correct |
3 |
Correct |
232 ms |
62584 KB |
Output is correct |
4 |
Correct |
233 ms |
62712 KB |
Output is correct |
5 |
Correct |
208 ms |
60652 KB |
Output is correct |
6 |
Correct |
191 ms |
65400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1083 ms |
36856 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1083 ms |
36856 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1085 ms |
27776 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |