oj.uz

Submission #564428

# Submission time Handle Problem Language Result Execution time Memory
564428 2022-05-19T07:57:41 Z hoanghq2004 Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 41140 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "garden.h"
#include "gardenlib.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 3e5 + 10;

vector <pair <int, int>> e[N];
vector <int> adj[N];
int to[N], root[N], deg[N], pos[N];
int in[N], out[N], comp[N];
int d[N], sz[N], flag[N];

int IsAnc(int u, int v) {
    return in[u] <= in[v] && out[v] <= out[u];
}
//void answer(int x) {
//    cout << x << '\n';
//}

void count_routes(int n, int m, int p, int r[][2], int q, int g[]) {
    vector <pair <int, int>> edges;
    for (int i = 0; i < m; ++i) {
        e[r[i][0]].push_back({r[i][1], i << 1});
        e[r[i][1]].push_back({r[i][0], i << 1 ^ 1});
        edges.push_back({r[i][0], r[i][1]});
        edges.push_back({r[i][1], r[i][0]});
    }
    memset(root, -1, sizeof(root));
    for (int i = 0; i < m * 2; ++i) {
        auto [u, v] = edges[i];
        to[i] = -1;
        for (auto [w, j]: e[v]) {
            if (i / 2 == j / 2) continue;
            to[i] = j;
            break;
        }
        if (to[i] == -1) to[i] = e[v][0].second;
    }
    for (int i = 0; i < m * 2; ++i) ++deg[to[i]];
    queue <int> Q;
    for (int i = 0; i < m * 2; ++i)
        if (!deg[i]) Q.push(i);
    while (Q.size()) {
        int v = Q.front();
        Q.pop();
        flag[v] = 1;
        int u = to[v];
        adj[u].push_back(v);
        if (!--deg[u]) Q.push(u);
    }
    int ti = 0, cnt = 0;
    function <void(int)> dfs = [&](int u) {
        in[u] = ++ti;
        comp[u] = cnt;
        if (d[u] == 0) root[u] = u;
        for (auto v: adj[u]) {
            root[v] = root[u];
            d[v] = d[u] + 1;
            dfs(v);
        }
        out[u] = ti;
    };
//    cout << edges[9].first << ' ' << edges[9].second << "sdfdsf\n";
//    for (int i = 0; i < m * 2; ++i) cout << adj[i].size() << ' ';
//    for (int i = 0; i < m * 2; ++i) cout << to[i] << ' ';
//    cout << '\n';
    for (int u = 0; u < m * 2; ++u) {
        if (flag[u] || comp[u]) continue;
        int v = u;
        ++cnt;
        int num = 0;
//        cout << u << "aa\n";
        do {
            pos[v] = num++;
            dfs(v);
            v = to[v];
        } while (u != v);
        do {
            sz[v] = num;
            v = to[v];
        } while (u != v);
    }
    vector <int> fin;
    for (int i = 0; i < e[p].size(); ++i) {
        fin.push_back(e[p][i].second);
        if (i == 1) break;
    }
    for (int id = 0; id < q; ++id) {
        int x = g[id];
        int ans = 0;
        for (int r = 0; r < n; ++r) {
            int u = e[r][0].second;
            for (auto v: fin) {
                if (comp[u] != comp[v]) continue;
                if (flag[u] && flag[v]) {
                    if (IsAnc(v, u) && (d[u] - d[v] == x)) ++ans;
                } else {
                    if (flag[v]) continue;
                    int y = x - d[u];
                    if (y < 0) continue;
                    int w = root[u];
                    int T = pos[v] - pos[w];
                    if (T < 0) T += sz[v];
                    if (y % sz[v] == T) ++ans;
                }
            }
        }
        answer(ans);
    }
}
//
//int main() {
//    int n, m, p;
//    cin >> n >> m >> p;
//    int r[m][2];
//    for (int i = 0; i < m; ++i) {
//        int u, v;
//        cin >> u >> v;
//        r[i][0] = u, r[i][1] = v;
//    }
//    int q;
//    cin >> q;
//    int g[q];
//    for (int i = 0; i < q; ++i) cin >> g[i];
//    count_routes(n, m, p, r, q, g);
//}

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:40:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |         auto [u, v] = edges[i];
      |              ^
garden.cpp:42:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |         for (auto [w, j]: e[v]) {
      |                   ^
garden.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for (int i = 0; i < e[p].size(); ++i) {
      |                     ~~^~~~~~~~~~~~~

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15828 KB Output is correct
2 Correct 10 ms 15828 KB Output is correct
3 Correct 9 ms 15824 KB Output is correct
4 Correct 9 ms 15564 KB Output is correct
5 Correct 9 ms 15628 KB Output is correct
6 Correct 10 ms 16088 KB Output is correct
7 Correct 9 ms 15572 KB Output is correct
8 Correct 9 ms 15688 KB Output is correct
9 Correct 12 ms 16584 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15828 KB Output is correct
2 Correct 10 ms 15828 KB Output is correct
3 Correct 9 ms 15824 KB Output is correct
4 Correct 9 ms 15564 KB Output is correct
5 Correct 9 ms 15628 KB Output is correct
6 Correct 10 ms 16088 KB Output is correct
7 Correct 9 ms 15572 KB Output is correct
8 Correct 9 ms 15688 KB Output is correct
9 Correct 12 ms 16584 KB Output is correct
10 Correct 10 ms 15560 KB Output is correct
11 Correct 21 ms 18920 KB Output is correct
12 Correct 50 ms 23796 KB Output is correct
13 Correct 42 ms 25900 KB Output is correct
14 Correct 164 ms 39988 KB Output is correct
15 Correct 192 ms 40764 KB Output is correct
16 Correct 162 ms 37112 KB Output is correct
17 Correct 145 ms 36488 KB Output is correct
18 Correct 48 ms 24356 KB Output is correct
19 Correct 157 ms 39936 KB Output is correct
20 Correct 177 ms 40708 KB Output is correct
21 Correct 162 ms 37532 KB Output is correct
22 Correct 150 ms 36528 KB Output is correct
23 Correct 158 ms 40988 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15828 KB Output is correct
2 Correct 10 ms 15828 KB Output is correct
3 Correct 9 ms 15824 KB Output is correct
4 Correct 9 ms 15564 KB Output is correct
5 Correct 9 ms 15628 KB Output is correct
6 Correct 10 ms 16088 KB Output is correct
7 Correct 9 ms 15572 KB Output is correct
8 Correct 9 ms 15688 KB Output is correct
9 Correct 12 ms 16584 KB Output is correct
10 Correct 10 ms 15560 KB Output is correct
11 Correct 21 ms 18920 KB Output is correct
12 Correct 50 ms 23796 KB Output is correct
13 Correct 42 ms 25900 KB Output is correct
14 Correct 164 ms 39988 KB Output is correct
15 Correct 192 ms 40764 KB Output is correct
16 Correct 162 ms 37112 KB Output is correct
17 Correct 145 ms 36488 KB Output is correct
18 Correct 48 ms 24356 KB Output is correct
19 Correct 157 ms 39936 KB Output is correct
20 Correct 177 ms 40708 KB Output is correct
21 Correct 162 ms 37532 KB Output is correct
22 Correct 150 ms 36528 KB Output is correct
23 Correct 158 ms 40988 KB Output is correct
24 Correct 9 ms 15572 KB Output is correct
25 Correct 212 ms 19016 KB Output is correct
26 Correct 343 ms 23900 KB Output is correct
27 Correct 2300 ms 25884 KB Output is correct
28 Correct 4226 ms 40248 KB Output is correct
29 Execution timed out 5057 ms 41140 KB Time limit exceeded
30 Halted 0 ms 0 KB -