#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
/*
//#include "garden.h"
//#include "gardenlib.h"
#include <stdio.h>
#include <stdlib.h>
#define MAX_M 1000000
#define MAX_Q 2000
static int N, M, P, Q;
static int R[MAX_M][2];
static int G[MAX_Q];
static int solutions[MAX_Q];
static int answers[MAX_Q];
static int answer_count;
inline
void my_assert(int e) {if (!e) abort();}
void read_input()
{
int i;
my_assert(3==scanf("%d %d %d",&N,&M,&P));
for(i=0; i<M; i++)
my_assert(2==scanf("%d %d",&R[i][0],&R[i][1]));
my_assert(1==scanf("%d",&Q));
for(i=0; i<Q; i++)
my_assert(1==scanf("%d",&G[i]));
for(i=0; i<Q; i++)
my_assert(1==scanf("%d",&solutions[i]));
}
void answer(int x)
{ cout << "+" << x << endl;
if(answer_count>=Q) {
printf("Incorrect. Too many answers.\n");
exit(0);
}
answers[answer_count] = x;
}
*/
const int Nn = 2e5 + 5;
int f[Nn], par[Nn][2], d[Nn][2], id[Nn][2], cur, to[Nn];
vector<int> V[Nn], from[Nn];
int calc(int t, int u) {
int U = u;
for(int i = 1; i <= cur; i++) f[i] = 0;
while(!f[u]) {
f[u] = 1;
u = to[u];
}
int sz = 0;
while(f[u] != 2) {
f[u] = 2;
u = to[u];
++sz;
}
u = U;
while(f[u] != 2) {
par[u][t] = 1;
f[u] = 2;
u = to[u];
}
u = U;
d[u][t] = 0;
queue<int> q; q.push(u);
while(q.size()) {
int u = q.front();
q.pop();
for(int i = 0; i < from[u].size(); i++) {
if(d[from[u][i]][t] <= d[u][t] + 1) continue;
d[from[u][i]][t] = d[u][t] + 1;
q.push(from[u][i]);
}
}
return sz;
}
void count_routes(int N, int M, int p, int R[][2], int Q, int G[])
{
++p;
for(int i = 1; i <= N; i++) {
id[i][0] = ++ cur;
id[i][1] = ++ cur;
}
for(int i = 0; i < M; i++) {
int u = R[i][0], v = R[i][1];
++u, ++v;
if(V[u].size() < 2) V[u].push_back(v);
if(V[v].size() < 2) V[v].push_back(u);
}
for(int i = 1; i <= N; i++) {
for(int j = 0; j < V[i].size(); j++) {
to[id[i][j]] = id[V[i][j]][0];
if(V[V[i][j]][0] == i && V[V[i][j]].size() > 1) {
to[id[i][j]] = id[V[i][j]][1];
}
from[to[id[i][j]]].push_back(id[i][j]);
}
}
for(int i = 1; i <= cur; i++) for(int t = 0; t < 2; t++) d[i][t] = 1e9;
vector<int> cyc(2);
cyc[0] = calc(0, id[p][0]); cyc[1] = calc(1, id[p][1]);
for(int i = 0; i < Q; i++) {
int cnt = 0;
for(int j = 1; j <= N; j++) {
if((!par[j][0] && G[i] % cyc[0] == d[id[j][0]][0]) || G[i] == d[id[j][0]][0]) ++cnt;
else if((!par[j][1] && G[i] % cyc[1] == d[id[j][0]][1]) || G[i] == d[id[j][0]][1]) ++cnt;
}
answer(cnt);
}
}
Compilation message
garden.cpp: In function 'int calc(int, int)':
garden.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i = 0; i < from[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:99:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int j = 0; j < V[i].size(); j++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
