oj.uz

Submission #30548

# Submission time Handle Problem Language Result Execution time Memory
30548 2017-07-24T14:57:07 Z top34051 Tropical Garden (IOI11_garden) C++14
49 / 100
 114 ms 27888 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;
        if(G[i]>=10000000) printf("%d",1/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:38:41: warning: division by zero [-Wdiv-by-zero]
         if(G[i]>=10000000) printf("%d",1/0);
                                        ~^~
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 4056 KB Output is correct
2 Correct 6 ms 4092 KB Output is correct
3 Correct 6 ms 4088 KB Output is correct
4 Correct 5 ms 3832 KB Output is correct
5 Correct 5 ms 3804 KB Output is correct
6 Correct 6 ms 4216 KB Output is correct
7 Correct 5 ms 3832 KB Output is correct
8 Correct 6 ms 4216 KB Output is correct
9 Correct 8 ms 4216 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4056 KB Output is correct
2 Correct 6 ms 4092 KB Output is correct
3 Correct 6 ms 4088 KB Output is correct
4 Correct 5 ms 3832 KB Output is correct
5 Correct 5 ms 3804 KB Output is correct
6 Correct 6 ms 4216 KB Output is correct
7 Correct 5 ms 3832 KB Output is correct
8 Correct 6 ms 4216 KB Output is correct
9 Correct 8 ms 4216 KB Output is correct
10 Correct 5 ms 3832 KB Output is correct
11 Correct 28 ms 10360 KB Output is correct
12 Correct 55 ms 14968 KB Output is correct
13 Incorrect 114 ms 27888 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4056 KB Output is correct
2 Correct 6 ms 4092 KB Output is correct
3 Correct 6 ms 4088 KB Output is correct
4 Correct 5 ms 3832 KB Output is correct
5 Correct 5 ms 3804 KB Output is correct
6 Correct 6 ms 4216 KB Output is correct
7 Correct 5 ms 3832 KB Output is correct
8 Correct 6 ms 4216 KB Output is correct
9 Correct 8 ms 4216 KB Output is correct
10 Correct 5 ms 3832 KB Output is correct
11 Correct 28 ms 10360 KB Output is correct
12 Correct 55 ms 14968 KB Output is correct
13 Incorrect 114 ms 27888 KB Output isn't correct
14 Halted 0 ms 0 KB -