Submission #203151

#TimeUsernameProblemLanguageResultExecution timeMemory
203151alexandra_udristoiuTropical Garden (IOI11_garden)C++14
49 / 100
50 ms25976 KiB
#include<fstream> #include<vector> #include<cstring> #include "garden.h" #include "gardenlib.h" #define DIM 150005 using namespace std; static int viz[DIM], dist[DIM], t[DIM], cic[DIM], nrcic[DIM], pos[DIM]; static pair<int, int> p[DIM][2]; static vector<int> v[DIM]; static void dfs(int nod){ viz[nod] = 1; for(int i = 0; i < v[nod].size(); i++){ int vecin = v[nod][i]; if(viz[vecin] == 0){ dist[vecin] = 1 + dist[nod]; dfs(vecin); } } } static void calcp(int i, int x, int y){ if(p[x][0].first == 0){ p[x][0] = make_pair(i, y); } else{ if(p[x][1].first == 0){ p[x][1] = make_pair(i, y); } } } static void calct(int x, pair<int, int> curr){ if(p[ curr.second ][0].first == curr.first && p[ curr.second ][1].first != 0){ t[x] = 2 * curr.second; } else{ t[x] = 2 * curr.second - 1; } } void count_routes(int n, int m, int d, int w[][2], int q, int g[]){ int i, x, k, j, sol; d++; for(i = 0; i < m; i++){ w[i][0]++; w[i][1]++; calcp(i + 1, w[i][0], w[i][1]); calcp(i + 1, w[i][1], w[i][0]); } for(i = 1; i <= n; i++){ calct(2 * i - 1, p[i][0]); if(p[i][1].first != 0){ calct(2 * i, p[i][1]); } else{ t[2 * i] = 2 * i; } } k = 0; for(i = 1; i <= 2 * n; i++){ v[ t[i] ].push_back(i); x = i; while(viz[x] == 0){ viz[x] = 1; pos[x] = i; x = t[x]; } if(pos[x] == i){ k++; while(viz[x] != 2){ viz[x] = 2; cic[x] = k; nrcic[k]++; x = t[x]; } } } for(i = 0; i < q; i++){ sol = 0; for(x = 2 * d - 1; x <= 2 * d; x++){ memset(viz, 0, sizeof(viz) ); dist[x] = 0; dfs(x); for(j = 1; j <= 2 * n; j += 2){ if(cic[x] != 0){ if(viz[j] == 1 && dist[j] <= g[i] && (dist[j] - g[i]) % nrcic[ cic[x] ] == 0){ sol++; } } else{ if(viz[j] == 1 && dist[j] == g[i]){ sol++; } } } } answer(sol); } }

Compilation message (stderr)

garden.cpp: In function 'void dfs(int)':
garden.cpp:13:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); i++){
                    ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...