結果
| 問題 | No.922 東北きりきざむたん |
| ユーザー |
 firiexp
|
| 提出日時 | 2019-11-08 22:35:46 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.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;
}