oj.uz

Submission #30540

# Submission time Handle Problem Language Result Execution time Memory
30540 2017-07-24T14:00:06 Z top34051 Tropical Garden (IOI11_garden) C++14
49 / 100
 107 ms 27868 KB 
#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;

#define maxn 150005

int par[maxn][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 5 ms 4088 KB Output is correct
2 Correct 6 ms 4088 KB Output is correct
3 Correct 6 ms 4116 KB Output is correct
4 Correct 5 ms 3876 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 6 ms 4108 KB Output is correct
7 Correct 5 ms 3832 KB Output is correct
8 Correct 6 ms 4092 KB Output is correct
9 Correct 8 ms 4208 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4088 KB Output is correct
2 Correct 6 ms 4088 KB Output is correct
3 Correct 6 ms 4116 KB Output is correct
4 Correct 5 ms 3876 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 6 ms 4108 KB Output is correct
7 Correct 5 ms 3832 KB Output is correct
8 Correct 6 ms 4092 KB Output is correct
9 Correct 8 ms 4208 KB Output is correct
10 Correct 5 ms 3960 KB Output is correct
11 Correct 29 ms 10428 KB Output is correct
12 Correct 55 ms 14884 KB Output is correct
13 Incorrect 107 ms 27868 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4088 KB Output is correct
2 Correct 6 ms 4088 KB Output is correct
3 Correct 6 ms 4116 KB Output is correct
4 Correct 5 ms 3876 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 6 ms 4108 KB Output is correct
7 Correct 5 ms 3832 KB Output is correct
8 Correct 6 ms 4092 KB Output is correct
9 Correct 8 ms 4208 KB Output is correct
10 Correct 5 ms 3960 KB Output is correct
11 Correct 29 ms 10428 KB Output is correct
12 Correct 55 ms 14884 KB Output is correct
13 Incorrect 107 ms 27868 KB Output isn't correct
14 Halted 0 ms 0 KB -