제출 #556109

#제출 시각아이디문제언어결과실행 시간메모리
556109stefantagaRailway (BOI17_railway)C++14
29 / 100
122 ms23980 KiB
#include <bits/stdc++.h> using namespace std; vector <int> v[100005]; int i,n,m,k; struct wow { int x,y; } muchie[100005]; int tin[100005],niv[100005],tout[100005]; struct AIB { int aib[400005]; int ub (int x) { return x&(-x); } void update(int poz,int val) { for (int i=poz; i<=2*n; i+=ub(i)) { aib[i]+=val; } return; } int query(int poz) { int i,sum=0; for (int i=poz; i>=1; i-=ub(i)) { sum+=aib[i]; } return sum; } } V; int rmq[200005][22]; void precompRMQ() { int i,j; for (i=1; i<=19; i++) { for (j=1; j<=n; j++) { rmq[j][i]=rmq[rmq[j][i-1]][i-1]; } } } int LCA(int x,int y) { if (niv[x]<niv[y]) { return LCA(y,x); } int dif = niv[x]-niv[y]; int p=1; for (i=0; i<=19; i++) { if (dif&p) { x=rmq[x][i]; } p=p*2; } if (x!=y) { for (i=19; i>=0; i--) { if (rmq[x][i]!=rmq[y][i]) { x=rmq[x][i]; y=rmq[y][i]; } } x=rmq[x][0]; } return x; } int q=0; void dfs(int x,int dad) { q++; rmq[x][0]=dad; niv[x]=niv[dad]+1; tin[x]=q; for (int i=0; i<v[x].size(); i++) { int nod = v[x][i]; if (nod!=dad) { dfs(nod,x); } } tout[x]=q; } bool compare(int a,int b) { return tin[a]>tin[b]; } int ceau[100005],loc[100005]; int main() { ios_base :: sync_with_stdio(false); cin.tie(0); #ifdef HOME ifstream cin("date.in"); ofstream cout("date.out"); #endif // HOME cin>>n>>m>>k; for (i=1; i<=n-1; i++) { int x,y; cin>>muchie[i].x>>muchie[i].y; x=muchie[i].x; y=muchie[i].y; v[x].push_back(y); v[y].push_back(x); } dfs(1,0); precompRMQ(); for (int teste =1 ; teste <=m ; teste++) { int nr; cin>>nr; for (int i=1; i<=nr; i++) { cin>>ceau[i]; } sort (ceau+1,ceau+nr+1,compare); ceau[nr+1]=ceau[1]; for (int i=1; i<=nr; i++) { int lca = LCA(ceau[i],ceau[i+1]); assert(lca); V.update(tin[ceau[i]],1); V.update(tin[ceau[i+1]],1); V.update(tin[lca],-2); } } for (i=1; i<=m; i++) { if (niv[muchie[i].x]<niv[muchie[i].y]) { loc[muchie[i].y]=i; } else { loc[muchie[i].x]=i; } } vector <int> solfin; for (i=1; i<=n; i++) { int val =V.query(tout[i]) - V.query(tin[i]-1); if(val>=2*k) { solfin.push_back(loc[i]); } } sort (solfin.begin(),solfin.end()); cout<<solfin.size()<<'\n'; for (i=0; i<solfin.size(); i++) { cout<<solfin[i]<<" "; } return 0; }

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

railway.cpp: In member function 'int AIB::query(int)':
railway.cpp:28:13: warning: unused variable 'i' [-Wunused-variable]
   28 |         int i,sum=0;
      |             ^
railway.cpp: In function 'void dfs(int, int)':
railway.cpp:85:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (int i=0; i<v[x].size(); i++)
      |                   ~^~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:161:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |     for (i=0; i<solfin.size(); 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...