oj.uz

Submission #30553

# Submission time Handle Problem Language Result Execution time Memory
30553 2017-07-24T15:30:14 Z top34051 Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 47308 KB 
#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
 
#define maxn 150005
 
int par[maxn*2][32];
int ans[2005];
vector<pair<int,int> > mn[maxn];
 
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    int i,j,x,y,now,cnt,temp;
    for(i=0;i<M;i++) {
        x = R[i][0]; y = R[i][1];
        if(mn[x].size()<2) mn[x].push_back({y,i+1});
        if(mn[y].size()<2) mn[y].push_back({x,i+1});
    }
//    for(x=0;x<N;x++) printf("%d : %d(%d) %d(%d)\n",x,mn[x][0].second,mn[x][0].first,((mn[x].size()==1) ? -1 : mn[x][1].second),((mn[x].size()==1) ? -1 : mn[x][1].first));
    for(x=0;x<N;x++) {
        //Best
        if(mn[x].size()>1) {
            if(mn[mn[x][1].first][0].second==mn[x][1].second) par[x*2+1][0] = mn[x][1].first*2+1;
            else par[x*2+1][0] = mn[x][1].first*2;
        }
        else {
            if(mn[mn[x][0].first][0].second==mn[x][0].second) par[x*2+1][0] = mn[x][0].first*2+1;
            else par[x*2+1][0] = mn[x][0].first*2;
        }
        //Second Best
        if(mn[mn[x][0].first][0].second==mn[x][0].second) par[x*2][0] = mn[x][0].first*2+1;
        else par[x*2][0] = mn[x][0].first*2;
//        printf("par %d(0) : %d(%d)   par %d(1) : %d(%d)\n",x,par[x*2][0]/2,par[x*2][0]%2,x,par[x*2+1][0]/2,par[x*2+1][0]%2);
    }
    for(i=1;i<=30;i++) for(x=0;x<2*N;x++) par[x][i] = par[par[x][i-1]][i-1];
    for(i=0;i<Q;i++) {
        ans[i] = 0;
        for(x=0;x<N;x++) {
            now = x*2; temp = G[i];
            for(j=0;j<=30;j++) {
                if(temp&1) now = par[now][j];
                temp/=2;
            }
//            printf("START %d : %d\n",x,now/2);
            if(now/2==P) ans[i]++;
        }
    }
    for(i=0;i<Q;i++) answer(ans[i]);
}

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:13:21: warning: unused variable 'cnt' [-Wunused-variable]
     int i,j,x,y,now,cnt,temp;
                     ^~~

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4216 KB Output is correct
2 Correct 6 ms 4220 KB Output is correct
3 Correct 6 ms 4216 KB Output is correct
4 Correct 6 ms 3832 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 6 ms 4236 KB Output is correct
7 Correct 5 ms 3960 KB Output is correct
8 Correct 6 ms 4216 KB Output is correct
9 Correct 8 ms 4216 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4216 KB Output is correct
2 Correct 6 ms 4220 KB Output is correct
3 Correct 6 ms 4216 KB Output is correct
4 Correct 6 ms 3832 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 6 ms 4236 KB Output is correct
7 Correct 5 ms 3960 KB Output is correct
8 Correct 6 ms 4216 KB Output is correct
9 Correct 8 ms 4216 KB Output is correct
10 Correct 6 ms 3960 KB Output is correct
11 Correct 29 ms 10360 KB Output is correct
12 Correct 56 ms 14900 KB Output is correct
13 Correct 166 ms 28592 KB Output is correct
14 Correct 262 ms 43084 KB Output is correct
15 Correct 257 ms 43544 KB Output is correct
16 Correct 164 ms 30820 KB Output is correct
17 Correct 109 ms 26532 KB Output is correct
18 Correct 51 ms 14904 KB Output is correct
19 Correct 237 ms 43048 KB Output is correct
20 Correct 251 ms 43544 KB Output is correct
21 Correct 167 ms 30768 KB Output is correct
22 Correct 112 ms 26532 KB Output is correct
23 Correct 284 ms 47308 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4216 KB Output is correct
2 Correct 6 ms 4220 KB Output is correct
3 Correct 6 ms 4216 KB Output is correct
4 Correct 6 ms 3832 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 6 ms 4236 KB Output is correct
7 Correct 5 ms 3960 KB Output is correct
8 Correct 6 ms 4216 KB Output is correct
9 Correct 8 ms 4216 KB Output is correct
10 Correct 6 ms 3960 KB Output is correct
11 Correct 29 ms 10360 KB Output is correct
12 Correct 56 ms 14900 KB Output is correct
13 Correct 166 ms 28592 KB Output is correct
14 Correct 262 ms 43084 KB Output is correct
15 Correct 257 ms 43544 KB Output is correct
16 Correct 164 ms 30820 KB Output is correct
17 Correct 109 ms 26532 KB Output is correct
18 Correct 51 ms 14904 KB Output is correct
19 Correct 237 ms 43048 KB Output is correct
20 Correct 251 ms 43544 KB Output is correct
21 Correct 167 ms 30768 KB Output is correct
22 Correct 112 ms 26532 KB Output is correct
23 Correct 284 ms 47308 KB Output is correct
24 Correct 16 ms 3960 KB Output is correct
25 Execution timed out 5002 ms 10564 KB Time limit exceeded
26 Halted 0 ms 0 KB -