Submission #14806

#	Time	Username	Problem	Language	Result	Execution time	Memory
14806		gs14004	Tropical Garden (IOI11_garden)	C++14	69 / 100	5055 ms	46480 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int,int> pi;

vector<pi> graph[150005];
int nxt[300005][30];
int low[150005];

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    memset(low,0x3f,sizeof(low));
    for (int i=0; i<M; i++) {
        for (int j=0; j<2; j++) {
            low[R[i][j]] = min(low[R[i][j]],i);
        }
        graph[R[i][0]].push_back(pi(R[i][1],i));
        graph[R[i][1]].push_back(pi(R[i][0],i));
    }
    for (int i=0; i<N; i++) {
        if(low[graph[i][0].first] == graph[i][0].second){
            nxt[2*i][0] = graph[i][0].first * 2 + 1;
        }
        else{
            nxt[2*i][0] = graph[i][0].first * 2;
        }
        if(graph[i].size() == 1){
            nxt[2*i+1][0] = nxt[2*i][0];
        }
        else{
            if(low[graph[i][1].first] == graph[i][1].second){
                nxt[2*i+1][0] = graph[i][1].first * 2 + 1;
            }
            else{
                nxt[2*i+1][0] = graph[i][1].first * 2;
            }
        }
    }
    for (int i=1; i<30; i++) {
        for (int j=0; j<2*N; j++) {
            nxt[j][i] = nxt[nxt[j][i-1]][i-1];
        }
    }
    for (int i=0; i<Q; i++) {
        int time = G[i];
        int cnt = 0;
        for (int j=0; j<N; j++) {
            int pos = 2*j;
            for (int k=0; k<30; k++) {
                if((time >> k) & 1){
                    pos = nxt[pos][k];
                }
            }
            if(pos == 2*P || pos == 2*P+1){
                cnt++;
            }
        }
        answer(cnt);
    }
}

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