Submission #1004500

#TimeUsernameProblemLanguageResultExecution timeMemory
10045000pt1mus23Railway (BOI17_railway)C++14
0 / 100
1046 ms34148 KiB
#pragma GCC optimize("O3", "inline") #include <bits/stdc++.h> using namespace std; #define ins insert #define pb push_back #define int long long int #define pii pair<int, int> #define endl '\n' #define drop(x) cout<<(x)<<endl; return; #define all(x) x.begin(),x.end() const int mod = 1e9 +7, sze = 1e5+10, inf = 2e18, prime = 23; vector<int> graph[sze]; int timer; int L; int n; vector<vector<int>> up; vector<int> giris,cixis; int depth[sze]; void dfs(int node,int p){ giris[node]=++timer; if(p!=node){ depth[node]=depth[p]+1; } up[node][0]=p; for(int i=1;i<=L;i++){ up[node][i]=up[up[node][i-1]][i-1]; } for(auto v:graph[node]){ if(v!=p){ dfs(v,node); } } cixis[node]=++timer; } bool checkata(int a,int b){// A, B'nin ATASIMI ? return (giris[a]<=giris[b] && cixis[a]>=cixis[b]); } int ata(int u,int v){ if(checkata(u,v)){ return u; } if(checkata(v,u)){ return v; } for(int i=L;i>=0;i--){ if(!checkata(up[u][i],v)){ u=up[u][i]; } } return up[u][0]; } void build(int root){ giris.resize(n+1); cixis.resize(n+1); timer=0; L = ceil(log2(n)); up.assign(n+1,vector<int>(L+1)); dfs(root,root); } int sub[sze]; int toxun[sze]; void mal(){ int m,k; vector<pair<int,int>> tracks; cin>>n>>m>>k; for(int i=0;i<n-1;i++){ int u,v;cin>>u>>v; graph[u].pb(v); graph[v].pb(u); tracks.pb({u,v}); } build(1); /* depthi en boyuk olan LCA , o LCA in altindaki en balaca depthli */ int mx = -1; int at = 0; vector<int> lst; for(int i=0;i<m;i++){ int s; cin>>s; int a,b; cin>>a>>b; lst.pb(a); lst.pb(b); // cout<<a<<" "<<b<<endl; int x = ata(a,b); // cout<<x<<endl; if(depth[x]>mx){ mx=depth[x]; at=x; } } for(auto v:lst){ int x = v; while(depth[x]>=mx){ toxun[x]++; x = up[x][0]; } } set<pair<int,int>> var; for(auto v:lst){ // cout<<v<<" : "<<toxun[v]<<endl; if(toxun[v]>=k){ if(v!=1){ int a = min(v,up[v][0]); int b = max(v,up[v][0]); var.ins({a,b}); } } } vector<int> ans; for(int i=0;i<n;i++){ int a = tracks[i].first; int b = tracks[i].second; if(var.count({min(a,b),max(a,b)})){ ans.pb(i+1); } } cout<<ans.size()<<endl; for(auto v:ans){ cout<<v<<" "; } cout<<endl; } signed main() { cin.tie(0)->sync_with_stdio(0); int tt = 1; // cin>>tt; while(tt--){ mal(); } }

Compilation message (stderr)

railway.cpp: In function 'void mal()':
railway.cpp:87:9: warning: variable 'at' set but not used [-Wunused-but-set-variable]
   87 |     int at = 0;
      |         ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...