結果
問題 | No.2638 Initial fare |
ユーザー |
|
提出日時 | 2024-02-19 21:29:46 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 195 ms / 2,000 ms |
コード長 | 7,517 bytes |
コンパイル時間 | 3,389 ms |
コンパイル使用メモリ | 273,048 KB |
実行使用メモリ | 63,860 KB |
最終ジャッジ日時 | 2024-09-29 01:25:25 |
合計ジャッジ時間 | 6,707 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
// #pragma GCC optimize("O3,unroll-loops")#include <bits/stdc++.h>// #include <x86intrin.h>using namespace std;#if __cplusplus >= 202002Lusing namespace numbers;#endiftemplate<class T>struct graph{using Weight_t = T;struct Edge_t{int from, to;T cost;};int n;vector<Edge_t> edge;vector<vector<int>> adj;function<bool(int)> ignore;graph(int n = 1): n(n), adj(n){assert(n >= 1);}graph(const vector<vector<int>> &adj, bool undirected = true): n((int)adj.size()), adj(n){assert(n >= 1);if(undirected){for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) if(u < v) link(u, v);}else for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) orient(u, v);}graph(const vector<vector<pair<int, T>>> &adj, bool undirected = true): n((int)adj.size()), adj(n){assert(n >= 1);if(undirected){for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) if(u < v) link(u, v, w);}else for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) orient(u, v, w);}graph(int n, vector<array<int, 2>> &edge, bool undirected = true): n(n), adj(n){assert(n >= 1);for(auto [u, v]: edge) undirected ? link(u, v) : orient(u, v);}graph(int n, vector<tuple<int, int, T>> &edge, bool undirected = true): n(n), adj(n){assert(n >= 1);for(auto [u, v, w]: edge) undirected ? link(u, v, w) : orient(u, v, w);}int operator()(int u, int id) const{#ifdef LOCALassert(0 <= id && id < (int)edge.size());assert(edge[id].from == u || edge[id].to == u);#endifreturn u ^ edge[id].from ^ edge[id].to;}int link(int u, int v, T w = {}){ // insert an undirected edgeint id = (int)edge.size();adj[u].push_back(id), adj[v].push_back(id), edge.push_back({u, v, w});return id;}int orient(int u, int v, T w = {}){ // insert a directed edgeint id = (int)edge.size();adj[u].push_back(id), edge.push_back({u, v, w});return id;}void clear(){for(auto [u, v, w]: edge){adj[u].clear();adj[v].clear();}edge.clear();ignore = {};}graph transposed() const{ // the transpose of the directed graphgraph res(n);for(auto &e: edge) res.orient(e.to, e.from, e.cost);res.ignore = ignore;return res;}int degree(int u) const{ // the degree (outdegree if directed) of u (without the ignoration rule)return (int)adj[u].size();}// The adjacency list is sorted for each vertex.vector<vector<int>> get_adjacency_list() const{vector<vector<int>> res(n);for(auto u = 0; u < n; ++ u) for(auto id: adj[u]){if(ignore && ignore(id)) continue;res[(*this)(u, id)].push_back(u);}return res;}void set_ignoration_rule(const function<bool(int)> &f){ignore = f;}void reset_ignoration_rule(){ignore = nullptr;}friend ostream &operator<<(ostream &out, const graph &g){for(auto id = 0; id < (int)g.edge.size(); ++ id){if(g.ignore && g.ignore(id)) continue;auto &e = g.edge[id];out << "{" << e.from << ", " << e.to << ", " << e.cost << "}\n";}return out;}};// Requires graphtemplate<class T>struct dfs_forest{int n;T base_dist;vector<T> dist;vector<int> pv;vector<int> pe;vector<int> order;vector<int> pos;vector<int> end;vector<int> size;vector<int> root_of;vector<int> root;vector<int> depth;vector<int> min_depth;vector<int> min_depth_origin;vector<int> min_depth_spanning_edge;// extra_edge[u]: adjacent edges of u which is not part of the spanning forest found during the last dfs-like run.vector<vector<int>> extra_edge;vector<int> was;dfs_forest(T base_dist = 0): base_dist(base_dist){ }void init(int n){this->n = n;pv.assign(n, -1);pe.assign(n, -1);order.clear();pos.assign(n, -1);end.assign(n, -1);size.assign(n, 0);root_of.assign(n, -1);root.clear();depth.assign(n, -1);min_depth.assign(n, -1);min_depth_origin.assign(n, -1);min_depth_spanning_edge.assign(n, -1);dist.assign(n, base_dist);extra_edge.assign(n, {});was.assign(n, -2);attempt = -1;}int attempt;// O(# of nodes reachable from u)template<class U, class F = plus<>>void _dfs(const graph<U> &g, int u, F UT = plus<>()){depth[u] = 0;dist[u] = base_dist;root_of[u] = u;root.push_back(u);pv[u] = pe[u] = -1;auto recurse = [&](auto self, int u)->void{was[u] = attempt;pos[u] = (int)order.size();order.push_back(u);size[u] = 1;min_depth[u] = depth[u];min_depth_origin[u] = u;min_depth_spanning_edge[u] = -1;for(auto id: g.adj[u]){if(id == pe[u] || g.ignore && g.ignore(id)) continue;int v = g(u, id);if(was[v] == attempt){if(min_depth[u] > depth[v]){min_depth[u] = depth[v];min_depth_spanning_edge[u] = id;}if(pe[u] != id) extra_edge[u].push_back(id);continue;}depth[v] = depth[u] + 1;dist[v] = UT(g.edge[id].cost, dist[u]);pv[v] = u;pe[v] = id;root_of[v] = root_of[u];self(self, v);size[u] += size[v];if(min_depth[u] > min_depth[v]){min_depth[u] = min_depth[v];min_depth_origin[u] = min_depth_origin[v];min_depth_spanning_edge[u] = min_depth_spanning_edge[v];}}end[u] = (int)order.size();};recurse(recurse, u);}// O(# of nodes reachable from src)template<class U, class F = plus<>>void dfs(const graph<U> &g, const vector<int> &src, F UT = plus<>()){assert(g.n <= n);root.clear(), order.clear();++ attempt;for(auto u: src){assert(0 <= u && u < g.n);if(was[u] != attempt) _dfs(g, u, UT);}}// O(n + m)template<class U, class F = plus<>>void dfs_all(const graph<U> &g, F UT = plus<>()){assert(g.n <= n);root.clear(), order.clear();++ attempt;for(auto u = 0; u < g.n; ++ u) if(was[u] != attempt) _dfs(g, u, UT);}// Check if u is visited during the last dfs-like call.bool visited(int u) const{assert(0 <= u && u < n);return was[u] == attempt;}// Check if u is an ancestor of v in some spanning tree.bool ancestor_of(int u, int v) const{assert(visited(u) && visited(v));return pos[u] <= pos[v] && end[v] <= end[u];}// Check if any cycle is found during the last dfs-like call.// If must_contain_root = true, the sought cycle is forced to contain one of the root of the trees.template<class U>optional<pair<int, vector<int>>> find_any_cycle(const graph<U> &g, bool must_contain_root = false) const{for(auto u: order) for(auto id: extra_edge[u]){int v = g(u, id);if(!ancestor_of(v, u) || must_contain_root && root_of[v] != v) continue;vector<int> cycle_edge;while(u != v) cycle_edge.push_back(pe[u]), u = pv[u];reverse(cycle_edge.begin(), cycle_edge.end());cycle_edge.push_back(id);return pair{v, cycle_edge};}return {};}};int main(){cin.tie(0)->sync_with_stdio(0);cin.exceptions(ios::badbit | ios::failbit);int n;cin >> n;graph<int> g(n);for(auto i = 0; i < n - 1; ++ i){int u, v;cin >> u >> v, -- u, -- v;g.link(u, v, 1);}dfs_forest<int> df;df.init(n);df.dfs(g, {0});vector<array<int, 4>> cnt(n);long long res = 0;for(auto u: df.order | ranges::views::reverse){++ cnt[u][0];for(auto id: g.adj[u]){if(id == df.pe[u]){continue;}int v = g(u, id);for(auto d = 1; d <= 2; ++ d){for(auto e = 0; e <= 2 - d; ++ e){res += 1LL * cnt[u][d] * cnt[v][e];}}for(auto d = 0; d <= 2; ++ d){cnt[u][d + 1] += cnt[v][d];}}for(auto d = 1; d <= 3; ++ d){res += cnt[u][d];}}cout << res << "\n";return 0;}/**/