Submission #447627

#	Time	Username	Problem	Language	Result	Execution time	Memory
447627		dxz05	Tropical Garden (IOI11_garden)	C++14	49 / 100	5068 ms	4992 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

const int MAXN = 155555;

using namespace std;

vector<int> g[MAXN];

int dfs(int v, int p, int k){
    if (k == 0) return v;
    if (g[v].size() == 1 || g[v][0] != p) return dfs(g[v][0], v, k - 1);
    return dfs(g[v][1], v, k - 1);
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    for (int i = 0; i < M; i++){
        g[R[i][0]].push_back(i);
        g[R[i][1]].push_back(i);
    }

    for (int i = 0; i < N; i++){
        if (g[i].size() < 2) continue;

        int j = min_element(g[i].begin(), g[i].end()) - g[i].begin();
        swap(g[i][0], g[i][j]);

        j = min_element(g[i].begin() + 1, g[i].end()) - g[i].begin();
        swap(g[i][1], g[i][j]);

        g[i].resize(2);
    }

    for (int i = 0; i < N; i++){
        int x = g[i][0];
        g[i][0] = (R[x][0] == i ? R[x][1] : R[x][0]);

        if (g[i].size() == 2){
            x = g[i][1];
            g[i][1] = (R[x][0] == i ? R[x][1] : R[x][0]);
        }

    }

    for (int it = 0; it < Q; it++){
        int ans = 0;
        for (int i = 0; i < N; i++){
            if (dfs(i, i, G[it]) == P) ans++;
        }
        answer(ans);
    }

}

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