제출 #282026

#제출 시각아이디문제언어결과실행 시간메모리
282026JoMeeRailway (BOI17_railway)C++17
7 / 100
1091 ms65272 KiB
#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; d > 0; i++){ if(d&1)idx = par[i][idx]; d/=2; } 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"; }

컴파일 시 표준 에러 (stderr) 메시지

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 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...