Submission #564428

#	Time	Username	Problem	Language	Result	Execution time	Memory
564428		hoanghq2004	Tropical Garden (IOI11_garden)	C++14	69 / 100	5057 ms	41140 KiB

garden

#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 (stderr)

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 / 49
• Subtask 2: 20 / 20
• Subtask 3: 0 / 31