제출 #237434

#제출 시각아이디문제언어결과실행 시간메모리
237434nicolaalexandra열대 식물원 (Tropical Garden) (IOI11_garden)C++14
100 / 100
2939 ms35192 KiB
#include <bits/stdc++.h> #include "garden.h" #include "gardenlib.h" #define DIM 300010 #define INF 2000000000 using namespace std; int nxt[DIM],dist[DIM],dist2[DIM]; vector <pair<int,int> > L[DIM]; vector <int> edg[DIM]; deque <int> c; /*void answer (int n){ cout<<n<<"\n"; }*/ void bfs (int start, int n, int dist[]){ int i; for (i=1;i<=2*n;i++) dist[i] = INF; c.clear(); c.push_back(start); dist[start] = 0; while (!c.empty()){ int nod = c.front(); c.pop_front(); for (auto vecin : edg[nod]){ if (dist[vecin] == INF){ dist[vecin] = 1 + dist[nod]; c.push_back(vecin); }}}} void count_routes (int n, int m, int dest, int r[][2], int q, int g[]){ int i,j; for (i=0;i<m;i++){ int x = r[i][0] + 1, y = r[i][1] + 1; L[x].push_back(make_pair(i,y)); L[y].push_back(make_pair(i,x)); } dest++; for (i=1;i<=n;i++) sort (L[i].begin(),L[i].end()); for (i=1;i<=n;i++){ /// duc muchia catre cea mai buna varianta j = L[i][0].second; if (L[j][0].second != i){ edg[j].push_back(i); /// graful o sa fie pe invers nxt[i] = j; } else { edg[j+n].push_back(i); nxt[i] = j+n; } /// a doua muchie if (L[i].size() >= 2){ j = L[i][1].second; if (L[j][0].second != i){ edg[j].push_back(i+n); nxt[i+n] = j; } else { edg[j+n].push_back(i+n); nxt[i+n] = j+n; } } else { j = L[i][0].second; if (L[j][0].second != i){ edg[j].push_back(i+n); nxt[i+n] = j; } else { edg[j+n].push_back(i+n); nxt[i+n] = j+n; }}} bfs (dest,n,dist); bfs (dest+n,n,dist2); //for (i=1;i<=2*n;i++) // cout<<dist[i]<<"\n"; /// am doua variante de a ajunge la destinatie => doua cicluri posibile int lg = dist[nxt[dest]] + 1; int lg2 = dist2[nxt[dest+n]] + 1; for (i=0;i<q;i++){ int k = g[i], sol = 0; for (j=1;j<=n;j++) if ( ((k >= dist[j]) && (k - dist[j]) % lg == 0) || (k >= dist2[j] && (k - dist2[j]) % lg2 == 0) ) sol++; answer(sol); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...