Submission #30534

#	Time	Username	Problem	Language	Result	Execution time	Memory
30534		top34051	Tropical Garden (IOI11_garden)	C++14	0 / 100	6 ms	4060 KiB

garden

#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});
        if(mn[y].size()<2) mn[y].push_back({x,i});
    }
    for(x=0;x<N;x++) {
        //Best
        if(mn[x].size()>1) {
            if(mn[mn[x][1].first][0].second==mn[x][0].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 (stderr)

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: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31