//IOI 2011 Day 1 Problem 1 Garden
// First 2 subtask solution 69 points
#include "garden.h"//for CMS
#include "gardenlib.h"//for CMS
//#include "grader.h" // for Yandex
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int inf=3e5+9,lg=32,MX=1e9+9;
int GoalNode,n;
int nxt[inf],sparse[inf][lg],dis[inf][2],Cycle[inf][2];
vector<pair<int,int> > v[inf];
vector<int> ReversedGraph[inf];
void dfs(int u,int d, bool round){
dis[u][round]=d;
for(auto v:ReversedGraph[u]){
if(v == GoalNode ){
int x=u;
while(x!=GoalNode)
Cycle[x][round]=d+1,x=nxt[x];
return ;
}
dfs(v,d+1,round);
}
}
int Queries(int k ){
for(int i=1;i<=n+n;i++)
dis[i][0]=dis[i][1]=MX,Cycle[i][0]=Cycle[i][1]=0;
dfs(GoalNode , 0 ,0 );
GoalNode+=n;
dfs(GoalNode,0,1);
GoalNode-=n;
int ret=0;
for(int i=1;i<=n;i++)
if( i != GoalNode)
if( dis[i][0] ==k || dis[i][1] == k || ( Cycle[i][0] && ( (k - dis[i][0])%Cycle[i][0]==0 ) ) || ( Cycle[i][1] && ( (k - dis[i][1])%Cycle[i][1]==0 ) ) )
ret++;
return ret;
}
int mn(int node){
pair<int,int> ret=make_pair(1e9,1e9);
for(auto o:v[node])
ret=min(ret,o);
return ret.second;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
GoalNode=++P;
n=N;
int ans=0;
for(int i=0;i<M;i++)
R[i][0]++,R[i][1]++,
v[R[i][0]].push_back(make_pair(i,R[i][1])),
v[R[i][1]].push_back(make_pair(i,R[i][0]) );
for(int i=1;i<=N;i++){
pair<int,int> temp[3];
temp[0]=temp[1]=temp[2]=make_pair(1e9,1e9);
//nxt[i] denotes the nxt node if we start from i or we didn't come to i from the most beautiful trial(adjacent to i)
// nxt[i+N] denotes the nxt node if we come to i from the most beautiful trail(adjacent to i)
for(auto o:v[i])
temp[2]=o,sort(temp,temp+3);
nxt[i]=temp[0].second+(N*(mn(temp[0].second)==i ) );
nxt[i+N]=(temp[1].second<1e9?temp[1].second+(N*(mn(temp[1].second)==i ) ):temp[0].second+(N*(mn(temp[0].second)==i ) ) );
}
for(int i=1;i<=n+n;i++)
ReversedGraph[nxt[i]].push_back(i);
for(int i=0;i<Q;i++)
answer( Queries(G[i]) );
}
Compilation message
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:65:9: warning: unused variable 'ans' [-Wunused-variable]
int ans=0;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
14712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
14712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
14712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
