제출 #554562

#제출 시각아이디문제언어결과실행 시간메모리
554562hegel123열대 식물원 (Tropical Garden) (IOI11_garden)C++14
컴파일 에러
0 ms0 KiB
#include<bits/stdc++.h> using namespace std; const int maxn = 150005; int n, m, x, a, b,q ; vector <pair<int, int>> G1[maxn]; vector <int> V[2*maxn+10]; vector <int> Vodw[2*maxn+10]; vector <int> Vpel[2*maxn+10]; int sp[2*maxn+10]; bool czycykl[2*maxn+10]; bool o[2*maxn+10]; bool czyzn[2*maxn+10]; int akt; int roz[2*maxn+10]; int odl[2][2*maxn+10]; int tab[2][2*maxn+10]; int pref[2][2*maxn+10]; void wczytaj(){ cin>>n>>m>>x; int w=m+10; for(int i=0; i<m; i++){ cin>>a>>b; G1[a].push_back({b, w}); G1[b].push_back({a, w}); w--; } } bool cmp(pair<int, int>& a, pair<int, int>& b){return a.second>b.second;} int sas; void con(){ for(int i=0; i<n; i++)sort(G1[i].begin(), G1[i].end(), cmp); for(int i=0; i<n; i++){ sas = G1[i][0].first; if(G1[sas][0].first == i)V[i].push_back(sas+maxn); else V[i].push_back(sas); if(G1[i].size() == 1) sas = G1[i][0].first; else sas = G1[i][1].first; if(G1[sas][0].first == i)V[i+maxn].push_back(sas+maxn); else V[i+maxn].push_back(sas); } } void fill(){ for(int i=0; i<n; i++){ Vodw[V[i][0]].push_back(i); Vpel[V[i][0]].push_back(i); Vpel[i].push_back(V[i][0]); Vodw[V[i+maxn][0]].push_back(i+maxn); Vpel[V[i+maxn][0]].push_back(i+maxn); Vpel[i+maxn].push_back(V[i+maxn][0]); } } int t = 1; void DFSsp(int ind){ sp[ind]=t; for(auto v : Vpel[ind]){ if(sp[v]==0)DFSsp(v); } } void DFS2(int ind){ if(czycykl[ind])return; else{ akt++; czyzn[sp[ind]]=true; czycykl[ind]=true; DFS2(V[ind][0]); } } void DFS(int ind){ if(czycykl[ind])return; o[ind]=true; sas = V[ind][0]; if(!o[sas])DFS(sas); else { if(!czyzn[sp[ind]]){ DFS2(sas); roz[sp[ind]]=akt; akt=0; } } } void BFS(int ind, int zj){ queue <int> Q; Q.push(ind); while(!Q.empty()){ int s = Q.front(); Q.pop(); for(auto v : Vodw[s]){ if(v==ind)continue; odl[zj][v]=odl[zj][s]+1; Q.push(v); } } } void solve(){ for(int i=0; i<n; i++){ if(sp[i]==0){DFSsp(i); t++;} if(sp[i+maxn]==0){DFSsp(i+maxn); t++;} } for(int i=0; i<n; i++){ if(!o[i])DFS(i); if(!o[i+maxn])DFS(i+maxn); } BFS(x, 0); BFS(x+maxn, 1); for(int i=0; i<n; i++){ tab[0][odl[0][i]]++; tab[1][odl[1][i]]++; } int dl = roz[sp[x]]; for(int i=0; i<2*maxn+9; i++){ if(i>dl)pref[0][i]=pref[0][i-dl]; pref[0][i]+=tab[0][i]; } dl = roz[sp[x+maxn]]; for(int i=0; i<2*maxn+9; i++){ if(i>dl)pref[1][i]=pref[1][i-dl]; pref[1][i]+=tab[1][i]; } } int zap(int z){ int wynik = 0; if(!czycykl[x]){ wynik+=tab[0][min(z, 2*maxn+9)]; } if(!czycykl[x+maxn]){ wynik+=tab[1][min(z, 2*maxn+9)]; } if(czycykl[x]){ int dl = roz[sp[x]]; if(z<dl){wynik+=tab[0][min(z, 2*maxn+9)];} else{ if(z%dl==0)wynik++; int reszta = z%dl; //for(int i = reszta; i<=min(z, 2*maxn+9); i+=dl){if(i!=0)wynik+=tab[0][i];} wynik+=pref[0][min(z, reszta + ((2*maxn+9-reszta)/dl)*dl + reszta )]; } } if(czycykl[x+maxn]){ int dl = roz[sp[x+maxn]]; if(z<dl){wynik+=tab[1][min(z, 2*maxn+9)];} else{ int reszta = z%dl; //for(int i = reszta; i<=min(z, 2*maxn+9); i+=dl){if(i!=0)wynik+=tab[1][i];} wynik+=pref[1][min(z, reszta + ((2*maxn+9-reszta)/dl)*dl + reszta )]; } } return wynik; } int idz(int ind, int dl, int pop){ //cout<<ind<<" "; if(dl==0)return ind; if(pop == G1[ind][0].first && G1[ind].size()>1)return idz(G1[ind][1].first, dl-1, ind); return idz(G1[ind][0].first, dl-1, ind); } int zapbrut(int dl){ int wynik=0; for(int i=0; i<n; i++){ //cout<<"wyruszamy: "; if(idz(i, dl, -1)==x)wynik++; //cout<<endl; } return wynik; } bool cmp1(pair<int, int>& a, pair <int, int>& b){return a.second>b.second;} int brutt(){ int a; while(q--){ cin>>a; cout<<zapbrut(a)<<" "; } return 0; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); wczytaj(); con(); fill(); solve(); //cout<<"wypisywanie: "<<pref[1][3]; cin>>q; //if(n<=1000 && m<= 10000 && q ==1){brutt(); return 0;} while(q--){ cin>>a; cout<<zap(a)<<" "; } return 0; }

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

/usr/bin/ld: /tmp/ccVfhFjm.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccIwDqYo.o:garden.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccVfhFjm.o: in function `main':
grader.cpp:(.text.startup+0x3f): undefined reference to `count_routes(int, int, int, int (*) [2], int, int*)'
collect2: error: ld returned 1 exit status