oj.uz

Submission #115376

# Submission time Handle Problem Language Result Execution time Memory
115376 2019-06-07T03:52:27 Z Runtime_error_ Tropical Garden (IOI11_garden) C++14
69 / 100
 320 ms 52956 KB 
//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;
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);
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7672 KB Output is correct
2 Correct 9 ms 7672 KB Output is correct
3 Correct 9 ms 7644 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 9 ms 7392 KB Output is correct
6 Correct 9 ms 7672 KB Output is correct
7 Correct 9 ms 7388 KB Output is correct
8 Correct 7 ms 7672 KB Output is correct
9 Correct 12 ms 7928 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7672 KB Output is correct
2 Correct 9 ms 7672 KB Output is correct
3 Correct 9 ms 7644 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 9 ms 7392 KB Output is correct
6 Correct 9 ms 7672 KB Output is correct
7 Correct 9 ms 7388 KB Output is correct
8 Correct 7 ms 7672 KB Output is correct
9 Correct 12 ms 7928 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct
11 Correct 35 ms 14124 KB Output is correct
12 Correct 65 ms 19376 KB Output is correct
13 Correct 114 ms 32784 KB Output is correct
14 Correct 266 ms 48624 KB Output is correct
15 Correct 266 ms 49320 KB Output is correct
16 Correct 201 ms 36876 KB Output is correct
17 Correct 149 ms 32768 KB Output is correct
18 Correct 63 ms 19276 KB Output is correct
19 Correct 265 ms 48684 KB Output is correct
20 Correct 279 ms 49300 KB Output is correct
21 Correct 207 ms 36720 KB Output is correct
22 Correct 159 ms 32576 KB Output is correct
23 Correct 320 ms 52956 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7672 KB Output is correct
2 Correct 9 ms 7672 KB Output is correct
3 Correct 9 ms 7644 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 9 ms 7392 KB Output is correct
6 Correct 9 ms 7672 KB Output is correct
7 Correct 9 ms 7388 KB Output is correct
8 Correct 7 ms 7672 KB Output is correct
9 Correct 12 ms 7928 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct
11 Correct 35 ms 14124 KB Output is correct
12 Correct 65 ms 19376 KB Output is correct
13 Correct 114 ms 32784 KB Output is correct
14 Correct 266 ms 48624 KB Output is correct
15 Correct 266 ms 49320 KB Output is correct
16 Correct 201 ms 36876 KB Output is correct
17 Correct 149 ms 32768 KB Output is correct
18 Correct 63 ms 19276 KB Output is correct
19 Correct 265 ms 48684 KB Output is correct
20 Correct 279 ms 49300 KB Output is correct
21 Correct 207 ms 36720 KB Output is correct
22 Correct 159 ms 32576 KB Output is correct
23 Correct 320 ms 52956 KB Output is correct
24 Incorrect 9 ms 7488 KB Output isn't correct
25 Halted 0 ms 0 KB -