Submission #598128

#	Time	Username	Problem	Language	Result	Execution time	Memory
598128		snasibov05	Tropical Garden (IOI11_garden)	C++14	69 / 100	262 ms	77228 KiB

garden

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

using namespace std;


void count_routes(int n, int m, int p, int r[][2], int q, int g[]){
    const int lg = 32;

    vector<vector<int>> ed(n, vector<int>(2, -1));
    for (int i = 0; i < m; ++i) {
        if (ed[r[i][0]][0] == -1) ed[r[i][0]][0] = r[i][1];
        else if (ed[r[i][0]][1] == -1) ed[r[i][0]][1] = r[i][1];

        if (ed[r[i][1]][0] == -1) ed[r[i][1]][0] = r[i][0];
        else if (ed[r[i][1]][1] == -1) ed[r[i][1]][1] = r[i][0];
    }

    for (int i = 0; i < n; ++i) {
        if (ed[i][1] == -1) ed[i][1] = ed[i][0];
    }

    vector<vector<int>> gg(2*n);
    for (int i = 0; i < n; ++i){
        int t1 = ed[i][0];
        if (ed[t1][0] == i) gg[i].push_back(t1 + n);
        else gg[i].push_back(t1);

        int t2 = ed[i][1];
        if (ed[t2][0] == i) gg[i + n].push_back(t2 + n);
        else gg[i + n].push_back(t2);
    }


    vector<vector<int>> up(2*n, vector<int>(lg));
    for (int i = 0; i < 2*n; ++i) up[i][0] = gg[i][0];
    for (int i = 1; i < lg; ++i){
        for (int j = 0; j < 2*n; ++j){
            up[j][i] = up[up[j][i-1]][i-1];
        }
    }

    int ans = 0;
    for (int i = 0; i < n; ++i){
        int cur = i;
        int k = g[0];
        int x = 0;
        while (k > 0){
            if (k % 2) cur = up[cur][x];
            x++; k /= 2;
        }
        if (cur == p || cur == p + n) ans++;
    }

    answer(ans);
}

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