This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<fstream>
#include<vector>
#include<cstring>
#include "garden.h"
#include "gardenlib.h"
#define DIM 300005
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |