제출 #890140

#제출 시각아이디문제언어결과실행 시간메모리
890140zeta7532Railway (BOI17_railway)C++17
36 / 100
177 ms36664 KiB
#include <bits/stdc++.h> #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") using namespace std; using ll = long long; const ll mod = 998244353; #define fi first #define se second #define rep(i,n) for(ll i=0;i<n;i++) #define all(x) x.begin(),x.end() #define faster ios::sync_with_stdio(false);cin.tie(nullptr) using Graph = vector<vector<ll>>; struct LCA{ vector<vector<ll>> par; vector<ll> dis; LCA(const Graph &G,ll root=0){init (G,root);} void init(const Graph &G,ll root=0){ ll v=G.size(); ll k=1; while((1<<k)<v) k++; par.assign(k,vector<ll>(v,-1)); dis.assign(v,-1); dfs(G,root,-1,0); for(ll i=0;i+1<k;i++){ for(ll j=0;j<v;j++){ if(par[i][j]<0) par[i+1][j]=-1; else par[i+1][j]=par[i][par[i][j]]; } } } void dfs(const Graph &G,ll v,ll p,ll d){ par[0][v]=p; dis[v]=d; for(ll nv:G[v]){ if(nv!=p) dfs(G,nv,v,d+1); } } ll query(ll u,ll v){ if(dis[u]<dis[v]) swap(u,v); ll K=par.size(); for(ll k=0;k<K;k++){ if((dis[u]-dis[v])>>k&1){ u=par[k][u]; } } if(u==v) return u; for(ll k=K-1;k>=0;k--){ if(par[k][u]!=par[k][v]){ u=par[k][u]; v=par[k][v]; } } return par[0][u]; } ll get_dis(ll u,ll v){return dis[u]+dis[v]-2*dis[query(u,v)];} }; vector<ll> bfs(vector<vector<ll>> G){ ll N=G.size(); vector<ll> dis(N,-1); dis[0]=0; queue<ll> que; que.push(0); while(!que.empty()){ ll v=que.front(); que.pop(); for(ll nv:G[v]){ if(dis[nv]!=-1) continue; dis[nv]=dis[v]+1; que.push(nv); } } return dis; } int main() { ll N,Q,K; cin >> N >> Q >> K; vector<ll> A(N-1),B(N-1); Graph G(N); rep(i,N-1){ cin >> A[i] >> B[i]; A[i]--,B[i]--; G[A[i]].push_back(B[i]); G[B[i]].push_back(A[i]); } vector<ll> dis=bfs(G); vector<ll> Eid(N,-1); rep(i,N-1){ if(dis[A[i]]>dis[B[i]]) Eid[A[i]]=i; if(dis[B[i]]>dis[A[i]]) Eid[B[i]]=i; } ll cnt=0; vector<ll> Vid(N); function<void(ll)> dfs=[&](ll v){ Vid[v]=cnt; cnt++; for(ll nv:G[v]){ if(dis[nv]<dis[v]) continue; dfs(nv); } }; dfs(0); vector<ll> imos(N,0); LCA ans(G); while(Q--){ ll M; cin >> M; vector<pair<ll,ll>> P(M); rep(i,M){ ll v; cin >> v; v--; P[i].fi=Vid[v]; P[i].se=v; } sort(all(P)); rep(i,M){ ll x=P[i].se; ll y=P[(i+1)%M].se; ll z=ans.query(x,y); imos[x]+=1; imos[y]+=1; imos[z]-=2; } } function<void(ll)> sum=[&](ll v){ ll par=-1; for(ll nv:G[v]){ if(dis[nv]<dis[v]){ par=nv; continue; } sum(nv); } if(par>=0) imos[par]+=imos[v]; }; sum(0); vector<ll> ANS; rep(i,N){ if(i==0) continue; if(imos[i]>=K*2) ANS.push_back(i); } cout << ANS.size() << endl; rep(i,ANS.size()){ cout << Eid[ANS[i]]+1 << " "; } cout << endl; return 0; }

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

railway.cpp: In function 'int main()':
railway.cpp:10:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define rep(i,n) for(ll i=0;i<n;i++)
......
  148 |     rep(i,ANS.size()){
      |         ~~~~~~~~~~~~          
railway.cpp:148:5: note: in expansion of macro 'rep'
  148 |     rep(i,ANS.size()){
      |     ^~~
#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...