#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
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 time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
3968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
3968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
3968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
