oj.uz

답안 #30548

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -