제출 #751138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
751138		tranxuanbach	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	100 / 100	3778 ms	55492 KiB

garden

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