Submission #237967

#TimeUsernameProblemLanguageResultExecution timeMemory
237967Ruxandra985Tropical Garden (IOI11_garden)C++14
0 / 100
7 ms3968 KiB
#include <bits/stdc++.h> #include "garden.h" #include "gardenlib.h" #define DIMN 150010 using namespace std; int tt[2][DIMN] , f[2][DIMN] , cod[2][DIMN] , poz[2][DIMN] , len_cycle[2][DIMN]; int dist[2][DIMN] , far[2][DIMN]; int prm[DIMN] , doi[DIMN]; vector <int> v[DIMN]; deque <pair <int,int> > dq; void step_back (int &state , int &curr){ if (tt[state][curr] > 0){ curr = tt[state][curr]; state = 0; } else { curr = -tt[state][curr]; state = 1; } } void count_routes(int n, int m, int p, int r[][2], int q, int g[]){ int i , curr , state , vecin , new_state , discovered , pc , old_state , old_curr; int dis , len , sol , j; p++; for (i = 0 ; i < m ; i++){ r[i][0]++; r[i][1]++; v[r[i][0]].push_back(r[i][1]); v[r[i][1]].push_back(r[i][0]); } for (i = 1 ; i <= n ; i++){ prm[i] = doi[i] = -1; cod[0][i] = cod[1][i] = 0; poz[0][i] = poz[1][i] = 0; tt[0][i] = tt[1][i] = 0; len_cycle[0][i] = len_cycle[1][i] = 0; } for (i = 0 ; i < m ; i++){ if (prm[r[i][0]] == -1) prm[r[i][0]] = r[i][1]; else if (doi[r[i][0]] == -1) doi[r[i][0]] = r[i][1]; if (prm[r[i][1]] == -1) prm[r[i][1]] = r[i][0]; else if (doi[r[i][1]] == -1) doi[r[i][1]] = r[i][0]; } /// ---------------------------------------------------------------------- dq.push_back(make_pair(0 , p)); f[0][p] = 1; while (!dq.empty()){ state = dq.front().first; curr = dq.front().second; dq.pop_front(); for (i = 0 ; i < v[curr].size() ; i++){ vecin = v[curr][i]; if (prm[vecin] == curr && !f[0][vecin]){ if ((state == 0 && prm[curr] != vecin) || (state == 1 && prm[curr] == vecin)){ dist[0][vecin] = 1 + dist[state][curr]; f[0][vecin] = 1; dq.push_back(make_pair(0 , vecin)); if (doi[vecin] == -1){ dist[1][vecin] = 1 + dist[state][curr]; f[1][vecin] = 1; dq.push_back(make_pair(1 , vecin)); } } } else if (prm[vecin] != curr && doi[vecin] == curr && !f[1][vecin]){ if ((state == 0 && prm[curr] != vecin) || (state == 1 && prm[curr] == vecin)){ dist[1][vecin] = 1 + dist[state][curr]; f[1][vecin] = 1; dq.push_back(make_pair(1 , vecin)); if (doi[vecin] == -1){ dist[0][vecin] = 1 + dist[state][curr]; f[0][vecin] = 1; dq.push_back(make_pair(0 , vecin)); } } } } } /// ----------------------------------------------------------------------------- /// imi cer scuze alexandra daca citesti asta for (i = 1 ; i <= n ; i++){ f[0][i] = f[1][i] = 0; } dq.push_back(make_pair(1 , p)); f[1][p] = 1; while (!dq.empty()){ state = dq.front().first; curr = dq.front().second; dq.pop_front(); for (i = 0 ; i < v[curr].size() ; i++){ vecin = v[curr][i]; if (prm[vecin] == curr && !f[0][vecin]){ if ((state == 0 && prm[curr] != vecin) || (state == 1 && prm[curr] == vecin)){ far[0][vecin] = 1 + far[state][curr]; f[0][vecin] = 1; dq.push_back(make_pair(0 , vecin)); if (doi[vecin] == -1){ far[1][vecin] = 1 + far[state][curr]; f[1][vecin] = 1; dq.push_back(make_pair(1 , vecin)); } } } else if (prm[vecin] != curr && doi[vecin] == curr && !f[1][vecin]){ if ((state == 0 && prm[curr] != vecin) || (state == 1 && prm[curr] == vecin)){ far[1][vecin] = 1 + far[state][curr]; f[1][vecin] = 1; dq.push_back(make_pair(1 , vecin)); if (doi[vecin] == -1){ far[0][vecin] = 1 + far[state][curr]; f[0][vecin] = 1; dq.push_back(make_pair(0 , vecin)); } } } } } /// mai fa un bfs aici ^^ /// daca in nod ajungi pe muchia prm[nod] , o iei pe doi[nod], daca ea exista /// state = 0, esti libera sa o iei pe prm for (i = 1 ; i <= n ; i++){ curr = i; state = 0; pc = 1; //printf ("\n\n%d\n\n" , i); while (!poz[state][curr]){ //printf ("%d %d\n" , curr , state); poz[state][curr] = pc; pc++; if (state == 0 || doi[curr] == -1){ vecin = prm[curr]; if (prm[vecin] == curr && doi[vecin] != -1) new_state = 1; else new_state = 0; } else { vecin = doi[curr]; if (prm[vecin] == curr && doi[vecin] != -1) new_state = 1; else new_state = 0; } /// din state, curr ----> new_state , vecin if (!poz[new_state][vecin]) tt[new_state][vecin] = (state == 0 ? curr : -curr); else { old_state = state; old_curr = curr; } state = new_state; curr = vecin; } /// ai ajuns undeva unde ai mai fost if (!cod[state][curr]){ /// am descoperit acum un ciclu discovered = pc - poz[state][curr]; cod[state][curr] = discovered; state = old_state; curr = old_curr; old_state = new_state; old_curr = vecin; while (curr != old_curr || state != old_state){ cod[state][curr] = discovered; step_back(state , curr); } /// ------------------------------------------------------------------- if (state == 0 && curr == i) continue; step_back(state , curr); dis = 1; while (curr != i || state != 0){ len_cycle[state][curr] = discovered; cod[state][curr] = -dis; dis++; step_back(state , curr); } len_cycle[state][curr] = discovered; cod[state][curr] = -dis; } else { /// am dat de un drum deja descoperit if (pc == 1) continue; if (cod[state][curr] > 0){ discovered = cod[state][curr]; dis = 1; } else { discovered = len_cycle[state][curr]; dis = -cod[state][curr] + 1; } state = old_state; curr = old_curr; while (curr != i || state != 0){ len_cycle[state][curr] = discovered; cod[state][curr] = -dis; dis++; step_back(state , curr); } len_cycle[state][curr] = discovered; cod[state][curr] = -dis; } } /// cred ca am terminat precalcularea for (i = 0 ; i < q ; i++){ len = g[i]; sol = 0; for (j = 1 ; j <= n ; j++){ //printf ("%d %d %d\n" , j , cod[0][j] , dist[0][j]); if (cod[0][j] > 0){ /// esti in ciclu if (dist[0][j] + 1 == (len + 1) % cod[0][j] || far[0][j] + 1 == (len + 1) % cod[0][j]) sol++; } else { /// verifica if (len <= -cod[0][j]){ if (dist[0][j] == len || far[0][j] == len) sol++; } else { len += cod[0][j]; len++; if (dist[0][j] + 1 == len % (len_cycle[0][j]) || far[0][j] + 1 == len % (len_cycle[0][j])) sol++; len = g[i]; } } } answer(sol); } }

Compilation message (stderr)

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:70:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0 ; i < v[curr].size() ; i++){
                      ~~^~~~~~~~~~~~~~~~
garden.cpp:122:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0 ; i < v[curr].size() ; i++){
                      ~~^~~~~~~~~~~~~~~~
garden.cpp:273:30: warning: 'old_curr' may be used uninitialized in this function [-Wmaybe-uninitialized]
             while (curr != i || state != 0){
                    ~~~~~~~~~~^~~~~~~~~~~~~
garden.cpp:273:30: warning: 'old_state' may be used uninitialized in this function [-Wmaybe-uninitialized]
garden.cpp:225:37: warning: 'new_state' may be used uninitialized in this function [-Wmaybe-uninitialized]
             while (curr != old_curr || state != old_state){
                    ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
garden.cpp:225:37: warning: 'vecin' may be used uninitialized in this function [-Wmaybe-uninitialized]
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...