| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 16402 | comet | Tropical Garden (IOI11_garden) | C++98 | 0 ms | 0 KiB |
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 "garden.h"
#include "gardenlib.h"
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
struct edge{
int u,c;
};
struct state{
int v,c,D;
};
#define pb push_back
typedef vector<int> vec;
typedef vector<edge> vecE;
vector<vecE> path;
vector<vec> z[2];
int Eyfa[150000];
int d[300000];
bool dir[300000];
void count_routes(int N, int M, int P, int R[][2], int q, int G[]){
path.assign(N,vecE());
for(int i=0;i<2;i++)z[i].assign(2*N,vec());
memset(Eyfa,-1,sizeof(Eyfa));
memset(d,0x3f,sizeof(d));
int INF=d[0];
for(int i=0;i<M;i++){
path[R[i][0]].pb(edge{R[i][1],i});
path[R[i][1]].pb(edge{R[i][0],i});
if(Eyfa[R[i][0]]<0)Eyfa[R[i][0]]=i;
if(Eyfa[R[i][1]]<0)Eyfa[R[i][1]]=i;
}
for(int i=0;i<N;i++){
int m[2]={1e9,},v[2]={path[i][0].u,};
for(int j=0;j<path[i].size();j++){
if(m[0]>path[i][j].c){
swap(m[0],m[1]);
swap(v[0],v[1]);
m[0]=path[i][j].c;
v[0]=path[i][j].u;
}
else if(m[1]>path[i][j].c){
m[1]=path[i][j].c;
v[1]=path[i][j].u;
}
}
if(m[1]==1e9)m[1]=m[0];
if(m[0]==Eyfa[v[0]])v[0]+=N;
if(m[1]==Eyfa[v[1]])v[1]+=N;
z[0][i].push_back(v[0]);
z[0][i+N].push_back(v[1]);
}
for(int i=0;i<2*N;i++){
for(int j=0;j<z[0][i].size();j++){
int u=z[0][i][j];
z[1][u].push_back(i);
}
}
queue<state> Q;
Q.push(state{P,0,0});
Q.push(state{P+N,0,1});
while(!Q.empty()){
int v=Q.front().v;
int c=Q.front().c;
int D=Q.front().D;
Q.pop();
for(int i=0;i<z[1][v].size();i++){
int u=z[1][v][i];
if(d[u]==INF){
d[u]=c+1;
dir[u]=D;
Q.push(state{u,d[u],D});
}
}
}
//for(int i=0;i<2*N;i++)printf("%d ",d[i]);
//puts("");
for(int i=0;i<q;i++){
int cnt=0;
for(int j=0;j<N;j++){
if(d[j]>G[i])continue;
if(d[j]==G[i]){
cnt++;
continue;
}
if(dir[j]){ // P+N
if(d[j]+d[P+N]>G[i])continue;
if(dir[P+N]){ /// P+N -> P+N
if((G[i]-d[j])%d[P+N]==0)cnt++;
}
else{ /// P+N -> P
if(dir[P]){ /// (P+N->P)->(P+N->P)
if((G[i]-d[j])%(d[P+N]+d[P])==0||(G[i]-d[j])%(d[P+N]+d[P])==d[P+N])cnt++;
}
else{ /// P+N->P->P
if((G[i]-d[j]-d[P+N])%d[P]==0)cnt++;
}
}
}
else{ // P
if(d[j]+d[P]>G[i])continue;
if(dir[P]){ /// P -> P+N
if(dir[P+N]){ /// P->P+N->P+N
if((G[i]-d[j]-d[P])%d[P+N]==0)cnt++;
}
else{ /// (P->P+N)->(P->P+N)
if((G[i]-d[j]-d[P])%(d[P]+d[P+N])==0||(G[i]-d[j]-d[P])%(d[P]+d[P+N])==d[P])cnt++;
}
}
else{ /// P -> P
if((G[i]-d[j])%d[P]==0)cnt++;
}
}
}
answer(cnt);
}
}