結果

問題 No.2638 Initial fare
ユーザー Aeren
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// #pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif
template<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 LOCAL
assert(0 <= id && id < (int)edge.size());
assert(edge[id].from == u || edge[id].to == u);
#endif
return u ^ edge[id].from ^ edge[id].to;
}
int link(int u, int v, T w = {}){ // insert an undirected edge
int 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 edge
int 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 graph
graph 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 graph
template<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;
}
/*
*/
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0