Submission #115370

#	Time	Username	Problem	Language	Result	Execution time	Memory
115370		Runtime_error_	Tropical Garden (IOI11_garden)	C++14	0 / 100	9 ms	7672 KiB

garden

//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: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;i++)
            sparse[i][j]=sparse[  sparse[i][j-1]  ][j-1];

    int length=G[0]-1;
    for(int i=1;i<=N;i++){
        int cur=i;
        for(int j=lg-1;j>=0;j--)
            if(length & (1<<j ) )
                cur=sparse[cur][j];
        ans+=(cur==P || cur==P+N);
    }

    answer(ans);
}

• Subtask 1: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31