oj.uz

Submission #1114328

# Submission time Handle Problem Language Result Execution time Memory
1114328 2024-11-18T15:06:47 Z usukhbaatar Tropical Garden (IOI11_garden) C++17
100 / 100
 4130 ms 39084 KB 
#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

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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 848 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 848 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 9 ms 5612 KB Output is correct
12 Correct 16 ms 8272 KB Output is correct
13 Correct 47 ms 33224 KB Output is correct
14 Correct 56 ms 18308 KB Output is correct
15 Correct 50 ms 18760 KB Output is correct
16 Correct 38 ms 16056 KB Output is correct
17 Correct 36 ms 14920 KB Output is correct
18 Correct 19 ms 7760 KB Output is correct
19 Correct 54 ms 18504 KB Output is correct
20 Correct 45 ms 18856 KB Output is correct
21 Correct 42 ms 15696 KB Output is correct
22 Correct 41 ms 14920 KB Output is correct
23 Correct 50 ms 20540 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 848 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 9 ms 5612 KB Output is correct
12 Correct 16 ms 8272 KB Output is correct
13 Correct 47 ms 33224 KB Output is correct
14 Correct 56 ms 18308 KB Output is correct
15 Correct 50 ms 18760 KB Output is correct
16 Correct 38 ms 16056 KB Output is correct
17 Correct 36 ms 14920 KB Output is correct
18 Correct 19 ms 7760 KB Output is correct
19 Correct 54 ms 18504 KB Output is correct
20 Correct 45 ms 18856 KB Output is correct
21 Correct 42 ms 15696 KB Output is correct
22 Correct 41 ms 14920 KB Output is correct
23 Correct 50 ms 20540 KB Output is correct
24 Correct 4 ms 336 KB Output is correct
25 Correct 361 ms 5960 KB Output is correct
26 Correct 656 ms 8488 KB Output is correct
27 Correct 1266 ms 33220 KB Output is correct
28 Correct 2025 ms 18592 KB Output is correct
29 Correct 2065 ms 19036 KB Output is correct
30 Correct 1633 ms 16200 KB Output is correct
31 Correct 1501 ms 14920 KB Output is correct
32 Correct 697 ms 7760 KB Output is correct
33 Correct 1945 ms 18612 KB Output is correct
34 Correct 2035 ms 19016 KB Output is correct
35 Correct 1965 ms 15804 KB Output is correct
36 Correct 2100 ms 14972 KB Output is correct
37 Correct 2644 ms 19452 KB Output is correct
38 Correct 4130 ms 39084 KB Output is correct