結果

問題 No.922 東北きりきざむたん
ユーザー kwm_t
提出日時 2023-05-21 15:11:05
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 183 ms / 2,000 ms
コード長 4,855 bytes
コンパイル時間 4,211 ms
コンパイル使用メモリ 265,188 KB
最終ジャッジ日時 2025-02-13 03:57:03
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
//const int INF = 1e9;
const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n-1); i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define endl "\n"
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
class Tree {
public:
Tree(int n, int root) : n(n), root(root) {
edge.resize(n);
for (int i = 0; i < MAXLOGV; i++) parent[i].resize(n);
depth.resize(n, -1);
}
// uv
// lca
void unite(int u, int v) {
edge[u].push_back(v);
edge[v].push_back(u);
}
// init
// lca
void init() {
rep(i, n) {
if (-1 != depth[i])continue;
dfs(i, -1, 0);
}
for (int k = 0; k + 1 < MAXLOGV; k++) {
for (int v = 0; v < n; v++) {
if (parent[k][v] < 0) parent[k + 1][v] = -1;
else parent[k + 1][v] = parent[k][parent[k][v]];
}
}
}
// uvlca
int lca(int u, int v) const {
if (depth[u] > depth[v]) swap(u, v);
for (int k = 0; k < MAXLOGV; k++) {
if ((depth[v] - depth[u]) >> k & 1) {
v = parent[k][v];
}
}
if (u == v) return u;
for (int k = MAXLOGV - 1; k >= 0; k--) {
if (parent[k][u] != parent[k][v]) {
u = parent[k][u];
v = parent[k][v];
}
}
return parent[0][u];
}
// un
int pare(int v, int n) {
if (depth[v] < n)return -1;
n = min(n, depth[v]);
int idx = MAXLOGV;
while (n) {
for (int i = idx - 1; i >= 0; --i) {
if (n < (1 << i))continue;
if (-1 == parent[i][v])continue;
n -= (1 << i);
v = parent[i][v];
idx = i;
break;
}
}
return v;
}
// uvd
int JumpOnTree(int u, int v, int d) {
if (0 == d)return u;
int distuv = dist(u, v);
if (distuv < d)return -1;
int l = lca(u, v);
if (l == u)return pare(v, distuv - d);
if (l == v)return pare(u, d);
int distlu = dist(l, u);
if (distlu >= d)return pare(u, d);
return pare(v, distuv - d);
}
// uv
// edge
int dist(int u, int v) const {
int p = lca(u, v);
return (depth[u] - depth[p]) + (depth[v] - depth[p]);
}
//wu,v
bool on_path(int u, int v, int w) {
return (dist(u, w) + dist(v, w) == dist(u, v));
}
int dfs(int v, int p, int d) {
int ret = 1;
parent[0][v] = p;
depth[v] = d;
for (int next : edge[v]) {
if (next == p) continue;
auto get = dfs(next, v, d + 1);
ret += get;
}
return ret;
}
static const int MAXLOGV = 25;
//
vector<vector<int>>edge;
//
int n;
//
int root;
//
vector<int> parent[MAXLOGV];
//
vector<int> depth;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q; cin >> n >> m >> q;
vector<vector<int>>to(n);
dsu uf(n);
Tree tree(n, 0);
rep(i, m) {
int a, b; cin >> a >> b; a--, b--;
to[a].push_back(b);
to[b].push_back(a);
uf.merge(a, b);
tree.unite(a, b);
}
tree.init();
long long ans = 0;
vector<int>cnt(n);
rep(i, q) {
int a, b; cin >> a >> b, a--, b--;
if (uf.same(a, b)) {
ans += tree.dist(a, b);
}
else {
cnt[a]++;
cnt[b]++;
}
}
vector<pair<long long, int>>memo(n);
vector<long long>result(n);
auto gs = uf.groups();
for (auto g : gs) {
int root = g[0];
// pre
auto dfs = [&](auto self, int v, int p = -1)->pair<long long, int> {
P ret = { 0,cnt[v] };
for (auto nv : to[v]) {
if (p == nv)continue;
auto get = self(self, nv, v);
ret.first += get.first + get.second;
ret.second += get.second;
}
return memo[v] = ret;
};
dfs(dfs, root);
int sz = memo[root].second;
result[root] = memo[root].first;
// main
auto dfs2 = [&](auto self, int v, int p = -1)->void {
if (-1 != p) {
result[v] = result[p];
result[v] += sz - 2 * memo[v].second;
}
for (auto nv : to[v]) {
if (p == nv)continue;
self(self, nv, v);
}
};
dfs2(dfs2, root);
long long val = LINF;
for (int v : g) {
chmin(val, result[v]);
}
ans += val;
}
cout << ans << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0