Submission #1238770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238770		nastya_an	Tropical Garden (IOI11_garden)	C++20	0 / 100	0 ms	576 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define cin(v) \
    for (auto &el : v) { cin >> el; }
#define cout(v)                               \
    for (auto &el : v) { cout << el << " "; } \
    cout << "\n";

using namespace std;
using ll = long long;
using db = double;
using ldb = long double;
const ldb EPS = 1e-9;
const ll LINF = 2e18;
const ll MOD = 1e9 + 7;
const ll MOD2 = 1072005019;
const ll MOD3 = 998244353;
const ldb PI = acos(-1.0);

vector<vector<int>> g;
vector<int> nxt, used, len_cycle, cycle_num_vert, first_vert, len_to_cycle, type_cycle, in_cycle_;
bool in_cycle = 0;
int first_vert_cur_cycle = -1, len = 0, type = 0;
vector<int> cycle;


void dfs(int v) {
    if (used[v] == 2) {
        return;
    }
    if (used[v] == 1) {
        in_cycle = 1;
        first_vert_cur_cycle = v;
        return;
    }
    used[v] = 1;
    dfs(nxt[v]);
    if (in_cycle) {
        in_cycle_[v] = 1;
        len++;
        cycle.push_back(v);
        first_vert[v] = v;
        type_cycle[v] = type;
    } else {
        len_to_cycle[v] = len_to_cycle[nxt[v]] + 1;
        first_vert[v] = first_vert[nxt[v]];
        type_cycle[v] = type_cycle[nxt[v]];
        len_cycle[v] = len;
    }
    if (v == first_vert_cur_cycle) {
        in_cycle = 0;
        first_vert_cur_cycle= -1;
    }
    used[v] = 2;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    int n, m, p;
    n = N;
    m = M;
    p = P;
    g.resize(n);
    for (int i = 0; i < m; i++) {
        int v = R[i][0], u = R[i][1];
        g[v].push_back(u);
        g[u].push_back(v);
    }
    nxt.resize(2 * n);
    used.resize(2 * n);
    len_cycle.resize(2 * n);
    cycle_num_vert.resize(2 * n);
    type_cycle.resize(2 * n);
    first_vert.resize(2 * n);
    len_to_cycle.resize(2 * n);
    in_cycle_.resize(2 * n);
    for (int v = 0; v < n; v++) {
        int to = g[v][0];
        if (g[to][0] == v && g[to].size() >= 2) {
            nxt[v] = to + n;
        } else {
            nxt[v] = to;
        }
        if (g[v].size() >= 2) {
            int to2 = g[v][1];
            if (g[to2][0] == v && g[to2].size() >= 2) {
                nxt[v + n] = to2 + n;
            } else {
                nxt[v + n] = to2;
            }
        } else {
            nxt[v + n] = nxt[v];
        }
    }
    g.resize(0);
    g.resize(2 * n);
    for (int v = 0; v < 2 * n; v++) {
        g[nxt[v]].push_back(v);
    }
    for (int v = 0; v < 2 * n; v++) {
        type = v;
        dfs(v);
        int i = 0;
        if (cycle.size()) {
            for (int v : cycle) {
                cycle_num_vert[v] = i;
                len_cycle[v] = len;
                i++;
            }
            cycle.resize(0);
        }
    }
    vector<int> len1(2 * n), len2(2 * n);
    vector<int> stack = {p};
    while (stack.size()) {
        int v = stack.back();
        stack.pop_back();
        for (int to : g[v]) {
            if (len1[to] > 0 || to == p) {
                continue;
            }
            len1[to] = len1[v] + 1;
            stack.push_back(to);
        }
    }
    stack.clear();
    stack.push_back(p + n);
    while (stack.size()) {
        int v = stack.back();
        stack.pop_back();
        for (int to : g[v]) {
            if (len2[to] > 0 || to == p + n) {
                continue;
            }
            len2[to] = len2[v] + 1;
            stack.push_back(to);
        }
    }
    int q = Q;
    for (int i = 0; i < q; i++) {
        int k = G[i];
        int ans = 0;
        //p
        if (in_cycle_[p]) {
            for (int v = 0; v < n; v++) {
                if (type_cycle[v] != type_cycle[p]) {
                    continue;
                }
                int v_ = first_vert[v];
                int len_ = len_to_cycle[v];
                if (cycle_num_vert[v_] >= cycle_num_vert[p]) {
                    len_ += cycle_num_vert[v_] - cycle_num_vert[p];
                } else {
                    len_ += len_cycle[v_] - (cycle_num_vert[p] - cycle_num_vert[v_]);
                }
                if (len_ <= k && k % len_cycle[v_] == len_ % len_cycle[v_]) {
                    ans++;
                }
            }
        } else {
            for (int v = 0; v < n; v++) {
                if (len1[v] >= k) {
                    ans++;
                }
            }
        }
        //p + n
        if (in_cycle_[p + n]) {
            for (int v = 0; v < n; v++) {
                if (type_cycle[v] != type_cycle[p + n]) {
                    continue;
                }
                int v_ = first_vert[v];
                int len_ = len_to_cycle[v];
                if (cycle_num_vert[v_] >= cycle_num_vert[p + n]) {
                    len_ += cycle_num_vert[v_] - cycle_num_vert[p + n];
                } else {
                    len_ += len_cycle[v_] - (cycle_num_vert[p + n] - cycle_num_vert[v_]);
                }
                if (len_ <= k && k % len_cycle[v_] == len_ % len_cycle[v_]) {
                    ans++;
                }
            }
        } else {
            for (int v = 0; v < n; v++) {
                if (len2[v] >= k) {
                    ans++;
                }
            }
        }
        answer(ans);
    }
    return;
}

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