제출 #605246

#제출 시각아이디문제언어결과실행 시간메모리
605246czhang2718Railway (BOI17_railway)C++17
29 / 100
120 ms27280 KiB
#include "bits/stdc++.h" using namespace std; #define rep(i,a,b) for(int i=a; i<=b; i++) const int N=1e5, K=18; int n, t; int a[N]; vector<pair<int,int>> adj[N]; int tin[N], tout[N]; int ans[N]; int par[N][K]; int up[N]; void dfs(int x){ tin[x]=++t; for(int i=1; i<K; i++) par[x][i]=par[par[x][i-1]][i-1]; for(auto e:adj[x]){ int k=e.first; if(k==par[x][0]) continue; par[k][0]=x; up[k]=e.second; dfs(k); } tout[x]=++t; } bool anc(int u, int v){ return tin[u]<=tin[v] && tout[u]>=tout[v]; } int lca(int u, int v){ if(anc(u,v)) return u; for(int k=K-1; k>=0; k--){ if(par[u][k]!=-1 && !anc(par[u][k], v)) u=par[u][k]; } return par[u][0]; } void dfs2(int x){ // cout << "to_add[" << x << "] " << ans[x] << "\n"; for(auto e:adj[x]){ int k=e.first; if(k==par[x][0]) continue; dfs2(k); ans[x]+=ans[k]; } } int main(){ cin.tie(0)->sync_with_stdio(0); int k, m; cin >> n >> m >> k; vector<vector<int>> nodes(n); for(int i=1; i<n; i++){ int u,v; cin >> u >> v; u--, v--; adj[u].push_back({v, i}); adj[v].push_back({u, i}); } for(int i=0; i<m; i++){ int cnt; cin >> cnt; while(cnt--){ int x; cin >> x; nodes[i].push_back(x-1); } } dfs(0); for(int c=0; c<m; c++){ sort(nodes[c].begin(), nodes[c].end(), [&](int i, int j){ return tin[i]<tin[j]; }); for(int j=0; j<nodes[c].size(); j++){ int x=nodes[c][j]; int prv=nodes[c][(nodes[c].size()+j-1)%(nodes[c].size())]; ans[nodes[c][j]]++; ans[lca(prv, x)]--; } } dfs2(0); vector<int> v; for(int i=1; i<n; i++){ if(ans[i]>=k) v.push_back(up[i]); } cout << v.size() << "\n"; for(int x:v) cout << x << " "; }

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

railway.cpp: In function 'int main()':
railway.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for(int j=0; j<nodes[c].size(); j++){
      |                      ~^~~~~~~~~~~~~~~~
#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...