oj.uz

Submission #751138

# Submission time Handle Problem Language Result Execution time Memory
751138 2023-05-31T05:46:58 Z tranxuanbach Tropical Garden (IOI11_garden) C++17
100 / 100
 3778 ms 55492 KB 
#include "garden.h"
#include "gardenlib.h"

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

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

struct functional_graph_processor{
    functional_graph_processor(const vector<int> &next): n((int)next.size()), cycle_id(n, -1), cycle_pos(n, -1), root(n, -1), depth(n, -1), abr(n){
        vector<int> was(n);
        for(auto u = 0; u < n; ++ u){
            if(was[u]) continue;
            int v = u;
            while(!was[v]){
                was[v] = true;
                v = next[v];
            }
            if(!~depth[v]){
                int w = v;
                vector<int> c;
                while(!~depth[w]){
                    cycle_id[w] = (int)cycle.size();
                    cycle_pos[w] = (int)c.size();
                    c.push_back(w);
                    root[w] = w;
                    depth[w] = 0;
                    w = next[w];
                }
                cycle.push_back(c);
                size.push_back((int)cycle.size());
            }
            auto dfs = [&](auto self, int u)->void{
                if(~depth[u]) return;
                int v = next[u];
                self(self, v);
                root[u] = root[v];
                ++ size[cycle_id[root[u]]];
                depth[u] = depth[v] + 1;
                abr[v].push_back(u);
            };
            dfs(dfs, u);
        }
    }
    // Requires graph
    template<class Graph>
    functional_graph_processor(const Graph &g){
        int n = g.n;
        assert(n == (int)g.edge.size());
        vector<int> pv(n, -1), state(n), on_cycle(n);
        vector<vector<int>> cycle;
        auto dfs = [&](auto self, int u, int p)->void{
            state[u] = 1;
            for(auto id: g.adj[u]){
                if(g.ignore && g.ignore(id)) continue;
                auto &e = g.edge[id];
                int v = u ^ e.from ^ e.to;
                if(v == p) continue;
                if(state[v] == 1){
                    cycle.emplace_back();
                    for(auto w = u; w != v; w = pv[w]){
                        cycle.back().push_back(w);
                        on_cycle[w] = true;
                    }
                    cycle.back().push_back(v);
                    on_cycle[v] = true;
                }
                else if(state[v] == 0){
                    pv[v] = u;
                    self(self, v, u);
                }
            }
            state[u] = 2;
        };
        for(auto u = 0; u < n; ++ u){
            if(state[u] != 2){
                assert(state[u] == 0);
                dfs(dfs, u, -1);
            }
        }
        vector<int> next(n, -1);
        auto dfs2 = [&](auto self, int u, int p)->void{
            for(auto id: g.adj[u]){
                if(g.ignore && g.ignore(id)) continue;
                auto &e = g.edge[id];
                int v = u ^ e.from ^ e.to;
                if(v == p || on_cycle[v]) continue;
                next[v] = u;
                self(self, v, u);
            }
        };
        for(auto &c: cycle){
            for(auto i = 0; i < (int)c.size(); ++ i) next[c[i]] = c[(i + 1) % (int)c.size()];
            for(auto u: c) dfs2(dfs2, u, -1);
        }
        *this = functional_graph_processor(next);
    }
    int n;
    vector<vector<int>> cycle; // main cycles
    vector<int> cycle_id; // id of the cycle it belongs to, -1 if not part of one
    vector<int> cycle_pos; // position in the cycle, -1 if not part of one
    vector<int> prev; // previous vertex in the cycle, -1 if not part of one
    vector<int> size; // size of the weakly connected component of the i-th main cycle
    vector<int> root; // first reachable node in the main cycle
    vector<int> depth; // # of edges from the main cycle
    vector<vector<int>> abr; // forest of arborescences of reversed edges not on the main cycle
};

const int N = 3e5 + 5;

struct edge{
    int from, to;
    int weight;
};

int n, m, t;
edge a[N];
vi adj[N];

pii b[N];
int nxt[N];
vi adj2[N];

int dist[3][N];

void reach_t(int j, const vi& vs){
    queue <int> qu;
    Fora(s, vs){
        dist[j][s] = 0;
        qu.emplace(s);
    }
    while (not qu.empty()){
        int u = qu.front(); qu.pop();
        Fora(v, adj2[u]){
            if (dist[j][v] == -1){
                dist[j][v] = dist[j][u] + 1;
                qu.emplace(v);
            }
        }
    }
}

void count_routes(int _n, int _m, int _t, int _edge[][2], int q, int ak[]){
    n = _n; m = _m; t = _t;
    For(i, 0, m){
        auto [u, v] = pair{_edge[i][0], _edge[i][1]};
        a[i * 2] = edge{u, v, i};
        adj[u].emplace_back(i * 2);
        a[i * 2 + 1] = edge{v, u, i};
        adj[v].emplace_back(i * 2 + 1);
    }
    For(u, 0, n){
        b[u] = {-1, -1};
        Fora(i, adj[u]){
            if (b[u].fi == -1 or a[b[u].fi].weight > a[i].weight){
                b[u].se = b[u].fi;
                b[u].fi = i;
            }
            else if (b[u].se == -1 or a[b[u].se].weight > a[i].weight){
                b[u].se = i;
            }
        }
    }
    For(i, 0, 2 * m){
        if (b[a[i].to].fi != (i ^ 1) or b[a[i].to].se == -1){
            nxt[i] = b[a[i].to].fi;
        }
        else{
            nxt[i] = b[a[i].to].se;
        }
        adj2[nxt[i]].emplace_back(i);
    }
    functional_graph_processor fgp(vi(nxt, nxt + 2 * m));
    vvi spec(1);
    For(i, 0, 2 * m){
        if (a[i].to != t){
            continue;
        }
        if (fgp.cycle_id[i] == -1){
            spec[0].emplace_back(i);
        }
        else{
            spec.emplace_back(vi{i});
        }
    }
    memset(dist, -1, sizeof(dist));
    For(j, 0, isz(spec)){
        reach_t(j, spec[j]);
    }

    For(i, 0, q){
        int k = ak[i] - 1;
        int ans = 0;
        For(u, 0, n){
            int id = b[u].fi;
            For(j, 0, isz(spec)){
                if (dist[j][id] == -1){
                    continue;
                }
                if (k == dist[j][id]){
                    ans++;
                    break;
                }
                if (j != 0 and k > dist[j][id] and (k - dist[j][id]) % isz(fgp.cycle[fgp.cycle_id[spec[j][0]]]) == 0){
                    ans++;
                    break;
                }
            }
        }
        answer(ans);
    }
}

/*
==================================================+
INPUT                                             |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18132 KB Output is correct
2 Correct 10 ms 18132 KB Output is correct
3 Correct 10 ms 18264 KB Output is correct
4 Correct 9 ms 17876 KB Output is correct
5 Correct 9 ms 17888 KB Output is correct
6 Correct 10 ms 18356 KB Output is correct
7 Correct 9 ms 17992 KB Output is correct
8 Correct 12 ms 18148 KB Output is correct
9 Correct 13 ms 19424 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18132 KB Output is correct
2 Correct 10 ms 18132 KB Output is correct
3 Correct 10 ms 18264 KB Output is correct
4 Correct 9 ms 17876 KB Output is correct
5 Correct 9 ms 17888 KB Output is correct
6 Correct 10 ms 18356 KB Output is correct
7 Correct 9 ms 17992 KB Output is correct
8 Correct 12 ms 18148 KB Output is correct
9 Correct 13 ms 19424 KB Output is correct
10 Correct 9 ms 17876 KB Output is correct
11 Correct 22 ms 23272 KB Output is correct
12 Correct 50 ms 29740 KB Output is correct
13 Correct 53 ms 37360 KB Output is correct
14 Correct 167 ms 53372 KB Output is correct
15 Correct 233 ms 54700 KB Output is correct
16 Correct 168 ms 48296 KB Output is correct
17 Correct 179 ms 47024 KB Output is correct
18 Correct 59 ms 29844 KB Output is correct
19 Correct 163 ms 53324 KB Output is correct
20 Correct 206 ms 54564 KB Output is correct
21 Correct 184 ms 48500 KB Output is correct
22 Correct 187 ms 46876 KB Output is correct
23 Correct 158 ms 55436 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18132 KB Output is correct
2 Correct 10 ms 18132 KB Output is correct
3 Correct 10 ms 18264 KB Output is correct
4 Correct 9 ms 17876 KB Output is correct
5 Correct 9 ms 17888 KB Output is correct
6 Correct 10 ms 18356 KB Output is correct
7 Correct 9 ms 17992 KB Output is correct
8 Correct 12 ms 18148 KB Output is correct
9 Correct 13 ms 19424 KB Output is correct
10 Correct 9 ms 17876 KB Output is correct
11 Correct 22 ms 23272 KB Output is correct
12 Correct 50 ms 29740 KB Output is correct
13 Correct 53 ms 37360 KB Output is correct
14 Correct 167 ms 53372 KB Output is correct
15 Correct 233 ms 54700 KB Output is correct
16 Correct 168 ms 48296 KB Output is correct
17 Correct 179 ms 47024 KB Output is correct
18 Correct 59 ms 29844 KB Output is correct
19 Correct 163 ms 53324 KB Output is correct
20 Correct 206 ms 54564 KB Output is correct
21 Correct 184 ms 48500 KB Output is correct
22 Correct 187 ms 46876 KB Output is correct
23 Correct 158 ms 55436 KB Output is correct
24 Correct 10 ms 17876 KB Output is correct
25 Correct 217 ms 23308 KB Output is correct
26 Correct 347 ms 29792 KB Output is correct
27 Correct 2247 ms 37440 KB Output is correct
28 Correct 1731 ms 53448 KB Output is correct
29 Correct 2819 ms 54708 KB Output is correct
30 Correct 1586 ms 48404 KB Output is correct
31 Correct 1557 ms 46988 KB Output is correct
32 Correct 244 ms 29952 KB Output is correct
33 Correct 1765 ms 53564 KB Output is correct
34 Correct 2729 ms 54668 KB Output is correct
35 Correct 1619 ms 48624 KB Output is correct
36 Correct 1822 ms 46908 KB Output is correct
37 Correct 1554 ms 55492 KB Output is correct
38 Correct 3778 ms 53032 KB Output is correct