結果
| 問題 | No.922 東北きりきざむたん |
| ユーザー |
 firiexp
|
| 提出日時 | 2019-11-08 22:35:46 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 6,815 bytes |
| コンパイル時間 | 946 ms |
| コンパイル使用メモリ | 97,124 KB |
| 最終ジャッジ日時 | 2024-11-14 21:49:40 |
| 合計ジャッジ時間 | 2,967 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:17:39: error: '::numeric_limits' has not been declared
17 | template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;
| ^~~~~~~~~~~~~~
main.cpp:17:55: error: expected primary-expression before '>' token
17 | template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;
| ^
main.cpp:17:61: error: no matching function for call to 'max()'
17 | template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;
| ~~~~~^~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/string:50,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/locale_classes.h:40,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/ios_base.h:41,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ios:42,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ostream:38,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/iostream:39,
from main.cpp:1:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
main.cpp:17:61: note: candidate expects 2 arguments, 0 provided
17 | template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;
| ~~~~~^~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:300:5: note: candidate: 'templat
ソースコード
#include <iostream>#include <algorithm>#include <iomanip>#include <map>#include <set>#include <queue>#include <stack>#include <numeric>#include <bitset>#include <cmath>static const int MOD = 1000000007;using ll = long long;using u32 = uint32_t;using namespace std;template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;class UnionFind {int n;vector<int> uni;int forest_size;public:explicit UnionFind(int n) : n(n), uni(static_cast<u32>(n), -1), forest_size(n) {};int root(int a){if (uni[a] < 0) return a;else return (uni[a] = root(uni[a]));}bool unite(int a, int b) {a = root(a);b = root(b);if(a == b) return false;if(uni[a] > uni[b]) swap(a, b);uni[a] += uni[b];uni[b] = a;forest_size--;return true;}int size(){ return forest_size; }int size(int i){ return -uni[root(i)]; }bool same(int a, int b) { return root(a) == root(b); }};template<typename M>class ReRooting {public:using T = typename M::T;using U = typename M::U;struct Node {int to, rev;U val;Node(int u, int v, U val) : to(u), rev(v), val(val) {};};int n;vector<vector<Node>> G;vector<vector<T>> dpl, dpr;vector<int> l, r;explicit ReRooting(int n) : n(n), G(n), dpl(n), dpr(n), l(n), r(n) {};void add_edge(int u, int v, const U &x) {G[u].emplace_back(v, G[v].size(), x);G[v].emplace_back(u, G[u].size()-1, x);}void add_edge(int u, int v, const U &x, const U &y) {G[u].emplace_back(v, G[v].size(), x);G[v].emplace_back(u, G[u].size()-1, y);}T dfs(int i, int par){while(l[i] != par && l[i] < G[i].size()){auto &e = G[i][l[i]];dpl[i][l[i] + 1] = M::f(dpl[i][l[i]], M::g(dfs(e.to, e.rev), e.val));++l[i];}while(r[i] != par && r[i] >= 0){auto &e = G[i][r[i]];dpr[i][r[i]] = M::f(dpr[i][r[i] + 1], M::g(dfs(e.to, e.rev), e.val));--r[i];}if(par < 0) return dpr[i].front();return M::f(dpl[i][par], dpr[i][par+1]);}vector<T> solve(){for (int i = 0; i < n; ++i) {dpl[i].assign(G[i].size()+1, M::e());dpr[i].assign(G[i].size()+1, M::e());l[i] = 0;r[i] = (int)G[i].size() - 1;}vector<T> ans(n);for (int i = 0; i < n; ++i) {ans[i] = dfs(i, -1);}return ans;}};struct M {using T = pair<ll, ll>;using U = ll;static T f(T a, T b) {return {a.first+b.first, a.second+b.second};}static T g(T a, U b) {return {a.first+a.second+b, a.second+b};}static T e() { return {0, 0}; }};class HeavyLightDecomposition {void dfs_sz(int v){for (auto &&u : G[v]) {if(u == par[v]) continue;par[u] = v; dep[u] = dep[v] + 1;dfs_sz(u);sub_size[v] += sub_size[u];if(sub_size[u] > sub_size[G[v][0]]) swap(u, G[v][0]);}}void dfs_hld(int v, int c, int &pos){id[v] = pos++;id_inv[id[v]]= v;tree_id[v] = c;for (auto &&u : G[v]) {if(u == par[v]) continue;head[u] = (u == G[v][0] ? head[v] : u);dfs_hld(u, c, pos);}}public:int n;vector<vector<int>> G;vector<int> par, dep, sub_size, id, id_inv, tree_id, head;explicit HeavyLightDecomposition(int n) : n(n), G(n), par(n), dep(n), sub_size(n, 1),id(n), id_inv(n), tree_id(n), head(n){}explicit HeavyLightDecomposition(vector<vector<int>> &G) :G(G), n(n), par(n), dep(n) , sub_size(n, 1), id(n), id_inv(n), tree_id(n), head(n) {}void add_edge(int u, int v){G[u].emplace_back(v);G[v].emplace_back(u);}void build(vector<int> roots = {0}){int c = 0, pos = 0;for (auto &&i : roots) {dfs_sz(i);head[i] = i;dfs_hld(i, c++, pos);}}int lca(int u, int v){while(true){if(id[u] > id[v]) swap(u, v);if(head[u] == head[v]) return u;v = par[head[v]];}}int distance(int u, int v){return dep[u] + dep[v] - 2*dep[lca(u, v)];}template<typename F>void query(int u, int v, const F &f){while(true){if(id[u] > id[v]) swap(u, v);f(max(id[head[v]], id[u]), id[v]+1);if(head[u] == head[v]) break;v = par[head[v]];}}template<typename F>void query_edge(int u, int v, const F &f){while(true){if(id[u] > id[v]) swap(u, v);f(max(id[head[v]], id[u]), id[v]+1);if(head[u] == head[v]) {if(u == v) break;f(id[u], id[v]+1);}else {v = par[head[v]];}}}template<typename T, typename Q, typename F>T query(int u, int v, const T &e, const Q &q, const F &f){T l = e, r = e;while(true){if(id[u] > id[v]) swap(u, v), swap(l, r);l = f(l, q(max(id[head[v]], id[u]), id[v]+1));if(head[u] != head[v]) v = par[head[v]];else break;}return f(l, r);}};int main() {int n, m, q;cin >> n >> m >> q;vector<vector<int>> G(n);UnionFind uf(n);HeavyLightDecomposition hld(n);for (int i = 0; i < m; ++i) {int u, v;scanf("%d %d", &u, &v);u--; v--;G[u].emplace_back(v);G[v].emplace_back(u);uf.unite(u, v);hld.add_edge(u, v);}vector<vector<int>> seibun(n);vector<int> roots;for (int i = 0; i < n; ++i) {seibun[uf.root(i)].emplace_back(i);if(i == uf.root(i)){roots.emplace_back(i);}}hld.build(roots);vector<int> val(n);vector<pair<int, int>> v;ll ans = 0;for (int i = 0; i < q; ++i) {int a, b;scanf("%d %d", &a, &b);a--; b--;if(uf.same(a, b)) ans += hld.distance(a, b);else val[a]++, val[b]++;}ReRooting<M> tree(n);for (int i = 0; i < n; ++i) {for (auto &&j : G[i]) {if(i < j) tree.add_edge(i, j, val[j], val[i]);}}auto ret = tree.solve();for (int i = 0; i < n; ++i) {if(seibun[i].size() >= 2){ll tmp = INF<ll>;for (auto &&j : seibun[i]) {tmp = min(tmp, ret[j].first);}ans += tmp;}}cout << ans << "\n";return 0;}