Submission #598188

#	Time	Username	Problem	Language	Result	Execution time	Memory
598188		snasibov05	Tropical Garden (IOI11_garden)	C++14	100 / 100	2519 ms	42108 KiB

garden

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

using namespace std;

void dfs(int cur, int t, vector<int>& d, int& c, vector<vector<int>>& ed){
    for (auto to : ed[cur]){
        if (to == t) {
            c = d[cur] + 1;
            continue;
        }
        d[to] = d[cur] + 1;
        dfs(to, t, d, c, ed);
    }
}

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

    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[t1 + n].push_back(i);
        else gg[t1].push_back(i);

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

    vector<int> d1(2*n, 2*n + 5); d1[p] = 0;
    vector<int> d2(2*n, 2*n + 5); d2[p + n] = 0;
    int c1 = 2*n + 5, c2 = 2*n + 5;
    dfs(p, p, d1, c1, gg);
    dfs(p + n, p + n, d2, c2, gg);

    for (int i = 0; i < q; ++i){
        int res = 0;
        for (int j = 0; j < n; ++j){
            if (d1[j] == g[i] || (c1 <= 2*n && g[i] - d1[j] > 0 && d1[j] <= 2*n && (g[i] - d1[j]) % c1 == 0)) res++;
            else if (d2[j] == g[i] || (c2 <= 2*n && g[i] - d2[j] > 0 && d2[j] <= 2*n && (g[i] - d2[j]) % c2 == 0)) res++;
        }
        answer(res);
    }
}

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