結果
| 問題 | No.922 東北きりきざむたん |
| ユーザー |
 Haar
|
| 提出日時 | 2019-11-14 01:44:44 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,978 bytes |
| コンパイル時間 | 3,393 ms |
| コンパイル使用メモリ | 238,456 KB |
| 実行使用メモリ | 37,684 KB |
| 最終ジャッジ日時 | 2024-09-21 21:18:51 |
| 合計ジャッジ時間 | 9,533 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
10,624 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 2 ms
5,376 KB |
| testcase_03 | AC | 2 ms
5,376 KB |
| testcase_04 | AC | 3 ms
5,376 KB |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | AC | 3 ms
5,376 KB |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | AC | 66 ms
37,684 KB |
| testcase_16 | TLE | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
ソースコード
#include <bits/stdc++.h>
#define LLI long long int
#define FOR(v, a, b) for(LLI v = (a); v < (b); ++v)
#define FORE(v, a, b) for(LLI v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(LLI v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define fst first
#define snd second
#define popcount __builtin_popcount
#define UNIQ(v) (v).erase(unique(ALL(v)), (v).end())
#define bit(i) (1LL<<(i))
#ifdef DEBUG
#include <misc/C++/Debug.cpp>
#else
#define dump(...) ((void)0)
#endif
#define gcd __gcd
using namespace std;
template <class T> constexpr T lcm(T m, T n){return m/gcd(m,n)*n;}
template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}
template <typename T, typename U> bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);}
template <typename T, typename U> bool chmax(T &a, const U &b){return (a<b ? a=b, true : false);}
template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}
struct Init{
Init(){
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(12);
cerr << fixed << setprecision(12);
}
}init;
template <typename Cost = int> class Edge{
public:
int from,to;
Cost cost;
Edge() {}
Edge(int to, Cost cost): to(to), cost(cost){}
Edge(int from, int to, Cost cost): from(from), to(to), cost(cost){}
Edge rev() const {return Edge(to,from,cost);}
friend ostream& operator<<(ostream &os, const Edge &e){
os << "(FROM: " << e.from << "," << "TO: " << e.to << "," << "COST: " << e.cost << ")";
return os;
}
};
template <typename T> using Graph = vector<vector<Edge<T>>>;
template <typename T> using Tree = vector<vector<Edge<T>>>;
template <typename C, typename T> void add_edge(C &g, int from, int to, T w){
g[from].push_back(Edge<T>(from, to, w));
}
template <typename C, typename T> void add_undirected(C &g, int a, int b, T w){
g[a].push_back(Edge<T>(a, b, w));
g[b].push_back(Edge<T>(b, a, w));
}
class UnionFind{
vector<int> parent, depth, size;
int count;
public:
UnionFind(){}
UnionFind(int n): parent(n), depth(n,1), size(n,1), count(n){
iota(ALL(parent),0);
}
int get_root(int i){
if(parent[i] == i) return i;
else return parent[i] = get_root(parent[i]);
}
bool is_same(int i, int j){return get_root(i) == get_root(j);}
int merge(int i, int j){
int ri = get_root(i), rj = get_root(j);
if(ri == rj) return ri;
else{
--count;
if(depth[ri] < depth[rj]){
parent[ri] = rj;
size[rj] += size[ri];
return rj;
}else{
parent[rj] = ri;
size[ri] += size[rj];
if(depth[ri] == depth[rj]) ++depth[ri];
return ri;
}
}
}
int get_size(int i){return size[get_root(i)];}
int count_group(){return count;}
};
template <typename T> class LCA{
private:
vector<vector<int>> parent;
int n, log2n;
void dfs(const Tree<T> &tree, int cur, int par, int d){
parent[cur][0] = par;
depth[cur] = d;
for(auto &e : tree[cur]){
if(e.to != par){
dist[e.to] = dist[cur] + e.cost;
dfs(tree, e.to, cur, d+1);
}
}
}
public:
vector<int> depth;
vector<T> dist;
LCA(){}
LCA(const Tree<T> &tree, int root):
n(tree.size()), depth(n), dist(n)
{
log2n = (int)ceil(log(n) / log(2)) + 1;
parent = vector<vector<int>>(n, vector<int>(log2n, 0));
dfs(tree, root, -1, 0);
REP(k,log2n-1){
REP(v,n){
if(parent[v][k] == -1) parent[v][k+1] = -1;
else parent[v][k+1] = parent[parent[v][k]][k];
}
}
}
int query(int a, int b){
if(depth[a] >= depth[b]) swap(a,b);
REP(k,log2n) if((depth[b] - depth[a]) >> k & 1) b = parent[b][k];
if(a == b) return a;
REV(k, log2n-1, 0) if(parent[a][k] != parent[b][k]){a = parent[a][k]; b = parent[b][k];}
return parent[a][0];
}
T distance(int a, int b){
return dist[a] + dist[b] - 2 * dist[query(a,b)];
}
};
template <typename F>
struct FixPoint : F{
explicit constexpr FixPoint(F &&f) noexcept : F(forward<F>(f)){}
template <typename... Args>
constexpr decltype(auto) operator()(Args &&... args) const {
return F::operator()(*this, forward<Args>(args)...);
}
};
template <typename F>
static inline constexpr decltype(auto) make_fix_point(F &&f){
return FixPoint<F>(forward<F>(f));
}
template <typename T>
struct Forest{
vector<Tree<T>> trees;
vector<int> tree_id;
vector<int> vertex_id;
vector<vector<int>> rid;
Forest(const Graph<T> &g){
int N = g.size();
UnionFind uf(N);
for(auto &v : g){
for(auto &e : v){
uf.merge(e.from, e.to);
}
}
int tree_num = uf.count_group();
trees.resize(tree_num);
tree_id.resize(N);
vertex_id.resize(N);
rid.resize(tree_num);
vector<int> temp;
for(int i = 0; i < N; ++i){
temp.push_back(uf.get_root(i));
}
sort(temp.begin(), temp.end());
temp.erase(unique(temp.begin(), temp.end()), temp.end());
for(int i = 0; i < N; ++i){
tree_id[i] = lower_bound(temp.begin(), temp.end(), uf.get_root(i)) - temp.begin();
vertex_id[i] = rid[tree_id[i]].size();
rid[tree_id[i]].push_back(i);
}
for(int i = 0; i < tree_num; ++i){
trees[i].resize(uf.get_size(temp[i]));
}
for(auto &v : g){
for(auto &e : v){
add_edge(trees[tree_id[e.from]], vertex_id[e.from], vertex_id[e.to], e.cost);
}
}
}
pair<int, int> forests_id(int i) const {
return make_pair(tree_id[i], vertex_id[i]);
}
int original_id(int i, int j) const {
return rid[i][j];
}
bool in_same_tree(int i, int j) const {
return tree_id[i] == tree_id[j];
}
int get_tree_num() const {
return trees.size();
}
};
int main(){
int N,M,Q;
while(cin >> N >> M >> Q){
Graph<LLI> g(N);
REP(i,M){
int u, v; cin >> u >> v;
--u, --v;
add_undirected(g, u, v, 1LL);
}
LLI ans = 0;
Forest<LLI> forest(g);
int tree_num = forest.get_tree_num();
vector<LCA<LLI>> lcas(tree_num);
REP(i,tree_num){
lcas[i] = LCA(forest.trees[i], 0);
}
vector<vector<bool>> plans(tree_num);
REP(i,tree_num){
plans[i] = vector<bool>(forest.trees[i].size());
}
REP(i,Q){
int a,b; cin >> a >> b;
--a, --b;
if(forest.in_same_tree(a, b)){
ans += lcas[forest.tree_id[a]].distance(forest.vertex_id[a], forest.vertex_id[b]);
}else{
plans[forest.tree_id[a]][forest.vertex_id[a]] = true;
plans[forest.tree_id[b]][forest.vertex_id[b]] = true;
}
}
dump(ans);
REP(i,tree_num){
auto &tree = forest.trees[i];
auto &plan = plans[i];
int L = tree.size();
vector<LLI> count(L);
auto dfs =
make_fix_point([&](auto &&f, int cur, int par) -> LLI{
LLI ret = 0;
count[cur] = 0;
for(auto &e : tree[cur]){
if(e.to == par) continue;
ret += f(e.to, cur);
count[cur] += count[e.to];
}
ret += count[cur];
if(plan[cur]) count[cur] += 1;
return ret;
});
LLI t = LLONG_MAX;
REP(j,L){
chmin(t, dfs(j, -1));
}
ans += t;
}
cout << ans << endl;
}
return 0;
}