結果
| 問題 | No.922 東北きりきざむたん |
| ユーザー |
 Haar
|
| 提出日時 | 2019-11-08 22:57:10 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,585 bytes |
| コンパイル時間 | 4,085 ms |
| コンパイル使用メモリ | 246,904 KB |
| 実行使用メモリ | 58,576 KB |
| 最終ジャッジ日時 | 2024-09-15 02:05:02 |
| 合計ジャッジ時間 | 10,916 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,816 KB |
| testcase_01 | AC | 2 ms
6,812 KB |
| testcase_02 | AC | 2 ms
6,812 KB |
| testcase_03 | AC | 2 ms
6,940 KB |
| testcase_04 | AC | 3 ms
6,948 KB |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | AC | 3 ms
6,940 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 | 78 ms
43,220 KB |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | AC | 372 ms
55,808 KB |
| testcase_26 | AC | 381 ms
55,712 KB |
| testcase_27 | AC | 372 ms
55,636 KB |
| testcase_28 | AC | 263 ms
51,388 KB |
| testcase_29 | AC | 410 ms
58,576 KB |
ソースコード
#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(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));
}
int main(){
int N,M,Q;
while(cin >> N >> M >> Q){
Graph<LLI> g(N);
UnionFind uf(N);
REP(i,M){
int u, v; cin >> u >> v;
--u, --v;
add_undirected(g, u, v, 1LL);
uf.merge(u, v);
}
LLI ans = 0;
vector<vector<int>> vertex(N);
map<int, pair<int,int>> new_node;
vector<Tree<LLI>> trees(N);
vector<LCA<LLI>> lcas(N);
REP(i,N) if(uf.get_root(i) == i) trees[i] = Tree<LLI>(uf.get_size(i));
REP(i,N){
int k = uf.get_root(i);
vertex[k].push_back(i);
new_node[i] = make_pair(k, vertex[k].size()-1);
}
REP(i,N){
for(auto &e : g[i]){
int k = uf.get_root(e.from);
add_edge(trees[k], new_node[e.from].snd, new_node[e.to].snd, 1LL);
}
}
REP(i,N){
if(trees[i].size()) lcas[i] = LCA(trees[i], 0);
}
//dump(trees);
vector<vector<bool>> plans(N);
REP(i,N){
plans[i] = vector<bool>(trees[i].size());
}
REP(i,Q){
int a,b; cin >> a >> b;
--a, --b;
if(uf.is_same(a, b)){
ans += lcas[uf.get_root(a)].distance(new_node[a].snd, new_node[b].snd);
}else{
plans[new_node[a].fst][new_node[a].snd] = true;
plans[new_node[b].fst][new_node[b].snd] = true;
}
}
dump(ans);
REP(i,N){
if(trees[i].size() == 0) continue;
int L = trees[i].size();
auto &tree = trees[i];
LLI s = 0;
REP(j,L) if(plans[i][j]) ++s;
dump(plans[i]);
dump(tree);
vector<LLI> count(L);
auto dfs1 =
make_fix_point([&](auto &&f, int cur, int par) -> LLI{
LLI ret = 0;
for(auto &e : tree[cur]){
if(e.to == par) continue;
ret += f(e.to, cur);
//if(plans[i][e.to]) ret += 1;
count[cur] += count[e.to];
}
ret += count[cur];
if(plans[i][cur]) count[cur] = 1;
return ret;
});
LLI dist = dfs1(0, -1);
dump(dist, s, count);
LLI t = dist;
auto dfs2 =
make_fix_point([&](auto &&f, int cur, int par, LLI d) -> void{
for(auto &e : tree[cur]){
if(e.to == par) continue;
LLI nd = d - count[e.to] + (s - count[e.to]);
chmin(t, nd);
//dump(nd);
f(e.to, cur, nd);
}
});
dfs2(0, -1, dist);
dump(t);
ans += t;
}
cout << ans << endl;
}
return 0;
}