//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>
using namespace std;
const int inf=3e5+9,lg=32;
int nxt[inf],sparse[inf][lg];
vector<pair<int,int> > v[inf];
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[])
{
P++;
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 ) ) );
sparse[i][0]=nxt[i];
sparse[i+N][0]=nxt[i+N];
}
for(int j=1;j<lg;j++)
for(int i=1;i<=N+N;i++)
sparse[i][j]=sparse[ sparse[i][j-1] ][j-1];
ll length=G[0];
for(int i=1;i<=N;i++){
int cur=i;
for(ll j=lg-1;j>=0;j--)
if( (length&(1ll<<j )) )
cur=sparse[cur][j];
ans+=(cur==P || cur==P+N);
}
answer(ans);
}
Compilation message
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:51:5: error: 'll' was not declared in this scope
ll length=G[0];
^~
garden.cpp:51:5: note: suggested alternative: 'lg'
ll length=G[0];
^~
lg
garden.cpp:54:16: error: expected ';' before 'j'
for(ll j=lg-1;j>=0;j--)
^
garden.cpp:54:23: error: 'j' was not declared in this scope
for(ll j=lg-1;j>=0;j--)
^
garden.cpp:55:18: error: 'length' was not declared in this scope
if( (length&(1ll<<j )) )
^~~~~~
garden.cpp:55:18: note: suggested alternative: 'le32toh'
if( (length&(1ll<<j )) )
^~~~~~
le32toh
