제출 #237393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
237393		nicolaalexandra	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	0 / 100	8 ms	5248 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define DIM 200010
using namespace std;

int dp[DIM*2][33];
vector <pair<int,int> > L[DIM];

/*void answer (int n){
    cout<<n<<"\n";
}*/

void count_routes (int n, int m, int dest, int r[][2], int q, int g[]){

    int i,j;
    for (i=0;i<m;i++){
        int x = r[i][0] + 1, y = r[i][1] + 1;
        L[x].push_back(make_pair(i,y));
        L[y].push_back(make_pair(i,x));
    }

    for (i=1;i<=n;i++)
        sort (L[i].begin(),L[i].end());

    for (i=1;i<=n;i++){

        j = L[i][0].second;
        if (L[j][0].second != i)
            dp[i][0] = j;
        else dp[i][0] = j + n;


        if (L[i].size() >= 2){
            j = L[i][1].second;
            if (L[j][0].second != i)
                dp[i+n][0] = j;
            else dp[i+n][0] = j+n;
        } else {
            j = L[i][0].second;
            if (L[j][0].second != i)
                dp[i+n][0] = j;
            else dp[i+n][0] = j+n;
        }

    }

    for (i=1;i<=2*n;i++)
        for (j=1;j<=30;j++)
            dp[i][j] = dp[dp[i][j-1]][j-1];

    for (i=0;i<q;i++){
        int k = g[i], sol = 0;
        for (j=1;j<=n;j++){
            int nod = j, val = k;
            for (int pas=30;pas>=0;pas--){
                if ((1<<pas) <= val){
                    nod = dp[nod][pas];
                    val -= (1<<pas);
                }
            }
            if (nod == dest + 1 || nod == dest + n + 1)
                sol++;
        }
        answer(sol);
    }

}

• Subtask 1: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31