QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#401605 | #7077. Sheep Village | hos_lyric | WA | 1ms | 3824kb | C++14 | 5.9kb | 2024-04-29 00:52:03 | 2024-04-29 00:52:04 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
// cycle = (us, is), us: in increasing order of depth
struct Cactus {
int n, m;
vector<pair<int, int>> edges;
vector<vector<int>> g;
int zeit;
vector<int> dis, fin, low, par, pari, dep;
int cyclesLen;
vector<pair<vector<int>, vector<int>>> cycles;
// n + m + |cycles|
int nn;
vector<int> isBridge;
vector<vector<int>> gg;
Cactus() {}
explicit Cactus(int n_) : n(n_), m(0), nn(0) {}
void ae(int u, int v) {
assert(0 <= u); assert(u < n);
assert(0 <= v); assert(v < n);
edges.emplace_back(u, v);
}
void dfs(int u, int p, int pi) {
dis[u] = low[u] = zeit++;
par[u] = p;
pari[u] = pi;
dep[u] = (!~p) ? 0 : (dep[p] + 1);
for (const int i : g[u]) if (pi != i) {
const int v = edges[i].first ^ edges[i].second ^ u;
if (!~dis[v]) {
dfs(v, u, i);
if (low[u] > low[v]) low[u] = low[v];
} else {
if (low[u] > dis[v]) low[u] = dis[v];
if (dis[u] > dis[v]) {
vector<int> us, is;
for (int w = u; ; w = par[w]) {
us.push_back(w);
if (w == v) break;
is.push_back(pari[w]);
}
reverse(us.begin(), us.end());
reverse(is.begin(), is.end());
is.push_back(i);
cycles.emplace_back(us, is);
}
}
}
fin[u] = zeit;
}
void build() {
m = edges.size();
g.assign(n, {});
for (int i = 0; i < m; ++i) {
g[edges[i].first].push_back(i);
g[edges[i].second].push_back(i);
}
zeit = 0;
dis.assign(n, -1);
fin.assign(n, -1);
low.assign(n, -1);
par.assign(n, -1);
pari.assign(n, -1);
dep.assign(n, -1);
cycles.clear();
for (int u = 0; u < n; ++u) if (!~dis[u]) dfs(u, -1, -1);
cyclesLen = cycles.size();
nn = n + m + cyclesLen;
isBridge.assign(m, 1);
gg.assign(nn, {});
for (int k = 0; k < cyclesLen; ++k) {
for (const int u : cycles[k].first) {
gg[u].push_back(n + m + k);
gg[n + m + k].push_back(u);
}
for (const int i : cycles[k].second) {
assert(isBridge[i]);
isBridge[i] = 0;
}
}
for (int i = 0; i < m; ++i) if (isBridge[i]) {
gg[edges[i].first].push_back(n + i);
gg[edges[i].second].push_back(n + i);
gg[n + i].push_back(edges[i].first);
gg[n + i].push_back(edges[i].second);
}
}
};
////////////////////////////////////////////////////////////////////////////////
int N, M, K;
vector<int> A, B;
vector<int> U, V;
vector<Int> W;
vector<int> fs;
Cactus cac;
Int ans;
int dfs(int x, int p) {
int ret = 0;
if (x < N) {
// vertex
const int u = x;
for (const int y : cac.gg[x]) if (p != y) {
ret += dfs(y, x);
}
ret += fs[u];
} else if (x < N + M) {
// bridge
const int i = x - N;
const int v = U[i] ^ V[i] ^ p;
ret = dfs(v, x);
ans += W[i] * abs(ret);
} else {
// cycle
const int k = x - N - M;
const auto &us = cac.cycles[k].first;
const auto &is = cac.cycles[k].second;
const int len = us.size();
/*
f: flow at us[0]
cost = \sum[l] W[l] |f + d[l]|
*/
vector<int> ds(len, 0);
for (int l = 1; l < len; ++l) {
ds[l] = ds[l - 1] + dfs(us[l], x);
}
Int sumW = 0;
vector<pair<int, Int>> dws(len);
for (int l = 0; l < len; ++l) {
sumW += W[is[l]];
dws[l] = make_pair(-ds[l], W[is[l]]);
}
// cerr<<"dws = "<<dws<<endl;
sort(dws.begin(), dws.end());
Int nowW = 0;
for (int j0 = 0; ; ++j0) {
nowW += dws[j0].second;
if (j0 && 2 * nowW >= sumW) {
const Int f = dws[j0 - 1].first;
Int cost = 0;
for (int j = 0; j < len; ++j) {
cost += dws[j].second * abs(f - dws[j].first);
}
ans += cost;
break;
}
}
ret = ds[len - 1];
}
// cerr<<"[dfs] "<<x<<" "<<p<<": "<<ret<<endl;
return ret;
}
int main() {
for (; ~scanf("%d%d%d", &N, &M, &K); ) {
A.resize(K); for (int k = 0; k < K; ++k) { scanf("%d", &A[k]); --A[k]; }
B.resize(K); for (int k = 0; k < K; ++k) { scanf("%d", &B[k]); --B[k]; }
U.resize(M);
V.resize(M);
W.resize(M);
for (int i = 0; i < M; ++i) {
scanf("%d%d%lld", &U[i], &V[i], &W[i]);
--U[i];
--V[i];
}
fs.assign(N, 0);
for (const int u : A) ++fs[u];
for (const int u : B) --fs[u];
cac = Cactus(N);
for (int i = 0; i < M; ++i) {
cac.ae(U[i], V[i]);
}
cac.build();
// cerr<<"cycles = "<<cac.cycles<<", cac.gg = "<<cac.gg<<endl;
ans = 0;
dfs(0, -1);
printf("%lld\n", ans);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3780kb
input:
5 8 4 2 2 3 3 4 4 5 5 1 2 1 2 1 1 1 3 1 3 1 1 1 4 1 4 1 1 1 5 1 5 1 1
output:
8
result:
ok single line: '8'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
5 5 3 1 3 3 5 2 4 1 2 3 2 3 1 3 4 1 4 5 4 5 1 1
output:
3
result:
ok single line: '3'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3824kb
input:
5 5 3 1 3 5 5 2 4 1 2 2 2 3 1 3 4 2 4 5 2 5 1 3
output:
6
result:
wrong answer 1st lines differ - expected: '4', found: '6'