Submission #1114328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114328		usukhbaatar	Tropical Garden (IOI11_garden)	C++17	100 / 100	4130 ms	39084 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;

int n, m, fn;
vector<vector<pair<int, int>>> a;
vector<int> g;
vector<bool> vis;
vector<bool> start;
vector<bool> finish;

void dfs(int u, int p, int i) {
    int x = (i << 1) + (p > u);
    if (x >= 0 && vis[x]) return;
    if (x != -1) vis[x] = 1;
    if (a[u].size() == 0) return;
    if (i != -1 && u == fn) finish[x] = 1; 
    int id = (a[u].size() == 1 || a[u][0].second != i) ? 0 : 1;
    int v = a[u][id].first;
    int j = a[u][id].second;
    int y = (j << 1) + (v < u);
    if (x != -1) {
        if (g[x] != -1 && g[x] != y) exit(1);
        g[x] = y;
    }
    else start[y] = 1;
    dfs(v, u, j);
}

vector<int> container[5];
vector<int> &comp = container[0];
vector<int> &level = container[1];
vector<int> &root = container[2];
vector<int> &order = container[3];
vector<int> &sz = container[4];
vector<vector<int>> cycles;

vector<int> path;
vector<bool> in_path;

void dfs(int u) {
    if (vis[u]) {
        if (in_path[u]) {
            cycles.push_back(vector<int>());
            int j = 0;
            for (int i = path.size() - 1; i >= 0; i--) {
                if (path[i] == u) {
                    j = i;
                    break;
                }
            }
            for (int i = j; i < path.size(); i++) {
                int v = path[i];
                order[v] = i - j;
                cycles.back().push_back(v);
                level[v] = 0;
                root[v] = v;
                comp[v] = cycles.size() - 1;
            }
        }
        return;
    }

    int v = g[u];
    if (v == -1) return;
    
    vis[u] = 1;
    path.push_back(u);
    in_path[u] = 1;    
    dfs(v);
    if (order[u] == -1) {
        comp[u] = comp[v];
        level[u] = level[v] + 1;
        root[u] = root[v];
    }
    in_path[u] = 0;
    path.pop_back();
}

void build() {
    for (int i = 0; i < 5; i++) {
        container[i].resize(m, -1);
    }
    vis.clear(); vis.resize(m, 0);
    in_path.resize(m, 0);

    for (int u = 0; u < m; u++) {
        if (start[u]) dfs(u);
    }
}

int jump(int u, int k) {
    int x = level[u];
    int y = cycles[comp[u]].size();
    if (x > k) return -1;
    k -= x;
    k %= y;
    u = root[u];
    int o = order[u] + k;
    o %= y;
    return cycles[comp[u]][o];
}

int check(int u, int k) {
    for (int i = 0; i < k; i++) {
        u = g[u];
        if (u == -1) return -1;
    }
    return u;
}

void count_routes(int N, int M, int P, int ed[][2], int q, int qry[]) {
    n = N, m = (M << 1), fn = P;
    a.resize(n);
    vis.resize(m, 0);
    g.resize(m, -1);
    start.resize(m, 0);
    finish.resize(m, 0);

    for (int i = 0; i < M; i++) {
        int u = ed[i][0], v = ed[i][1];
        if (a[u].size() < 2) a[u].push_back({v, i});
        if (a[v].size() < 2) a[v].push_back({u, i});
    }
    
    for (int u = 0; u < n; u++) {
        dfs(u, n, -1);
    }
    build();

    for (int i = 0; i < q; i++) {
        int ans = 0;
        for (int u = 0; u < m; u++) {
            if (start[u]) {
                int v = jump(u, qry[i] - 1);
                if (v == -1) v = check(u, qry[i] - 1);
                if (finish[v]) ans++;
            }
        }
        answer(ans);
    }
}

Compilation message (stderr)

garden.cpp: In function 'void dfs(int)':
garden.cpp:53:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             for (int i = j; i < path.size(); i++) {
      |                             ~~^~~~~~~~~~~~~

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