제출 #244687

#제출 시각아이디문제언어결과실행 시간메모리
244687kimbj0709Railway (BOI17_railway)C++14
0 / 100
124 ms49828 KiB
#include<bits/stdc++.h> using namespace std; #define maxn 100050 vector<vector<pair<int,int> > > adj(maxn); vector<int> cnt(maxn,0); vector<int> vect1; vector<int> seg(maxn*20,0); vector<int> depth(maxn,INT_MAX); vector<int> pos(maxn); int no_of_vertex,no_of_people,mini; void build(int node,int start,int end){ if(start==end){ seg[node] = vect1[start]; return; } int mid = (start+end)/2; build(node*2+1,start,mid); build(node*2+2,mid+1,end); if(depth[seg[node*2*2]]>depth[seg[node*2+1]]){ seg[node] = seg[node*2+1]; } else{ seg[node] = seg[node*2+2]; } } int query(int node,int start,int end,int rangemin,int rangemax){ if(start>=rangemin&&end<=rangemax){ return seg[node]; } if(start>rangemax||end<rangemin){ return -1; } int mid = (start+end)/2; int left = query(node*2+1,start,mid,rangemin,rangemax); int right = query(node*2+2,mid+1,end,rangemin,rangemax); if(left==-1){ return right; } if(right==-1){ return left; } if(depth[right]>depth[left]){ return left; } else{ return right; } } void dfs(int node,int parent,int d){ pos[node] = (int)vect1.size(); vect1.push_back(node); depth[node] = d; for(auto k:adj[node]){ if(k.first!=parent){ vect1.push_back(node); dfs(k.first,node,d+1); vect1.push_back(node); } } } vector<int> ans; void dfs2(int node,int parent,int last){ for(auto k:adj[node]){ if(k.first!=parent){ dfs2(k.first,node,k.second); cnt[node] += cnt[k.first]; } } if(cnt[node]>=mini){ ans.push_back(last); } } int32_t main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int no_of_input; int input1,input2,input3,input; cin >> no_of_vertex >> no_of_people >> mini; for(int i=0;i<no_of_vertex-1;i++){ cin >> input1 >> input2; adj[input1].push_back({input2,i}); adj[input2].push_back({input1,i}); } dfs(1,-1,0); build(0,0,vect1.size()-1); for(int i=0;i<no_of_people;i++){ cin >> no_of_input >> input1 >> input2; assert(no_of_input==2); int lca = query(0,0,vect1.size()-1,min(pos[input1],pos[input2]),max(pos[input1],pos[input2])); cnt[input1]++; cnt[input2]++; cnt[lca] -= 2; } /*for(int i=1;i<=no_of_vertex;i++){ for(int j=1;j<=no_of_vertex;j++){ cout << i << " " << j << " " << query(0,0,vect1.size()-1,min(pos[i],pos[j]),max(pos[i],pos[j])) << "\n"; } }*/ dfs2(1,-1,-1); for(int i=1;i<=no_of_vertex;i++){ assert(cnt[i]==0); } sort(ans.begin(),ans.end()); cout << ans.size() << '\n'; for(auto k:ans){ cout << k+1 << " "; } }

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

railway.cpp: In function 'int32_t main()':
railway.cpp:77:23: warning: unused variable 'input3' [-Wunused-variable]
     int input1,input2,input3,input;
                       ^~~~~~
railway.cpp:77:30: warning: unused variable 'input' [-Wunused-variable]
     int input1,input2,input3,input;
                              ^~~~~
#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...