| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 298606 |
2020-09-13T13:42:48 Z |
AM1648 |
Toll (APIO13_toll) |
C++17 |
|
1 ms |
384 KB |
/* be name khoda */
// #define long_enable
#include <iostream>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <fstream>
#include <set>
#include <map>
using namespace std;
#ifdef long_enable
typedef long long int ll;
#else
typedef int ll;
#endif
typedef pair<ll, ll> pii;
typedef pair<pii, ll> ppi;
typedef pair<ll, pii> pip;
typedef vector<ll> vi;
typedef vector<pii> vpii;
#define forifrom(i, s, n) for (ll i = s; i < n; ++i)
#define forirto(i, n, e) for (ll i = (n) - 1; i >= e; --i)
#define fori(i, n) forifrom (i, 0, n)
#define forir(i, n) forirto (i, n, 0)
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define smin(a, b) a = min(a, (b))
#define smax(a, b) a = max(a, (b))
#define debug(x) cout << #x << " -> " << (x) << endl
#define debug2(x, y) cout << #x << ' ' << #y << " -> " << (x) << ' ' << (y) << endl
#define debug3(x, y, z) cout << #x << ' ' << #y << ' ' << #z << " -> " << (x) << ' ' << (y) << ' ' << (z) << endl
#define debug4(x, y, z, t) cout << #x << ' ' << #y << ' ' << #z << ' ' << #t << " -> " << (x) << ' ' << (y) << ' ' << (z) << ' ' << (t) << endl
#define debuga(x, n) cout << #x << " -> "; fori (i1_da, n) { cout << (x)[i1_da] << ' '; } cout << endl
#define debugaa(x, n, m) cout << #x << " ->\n"; fori (i1_daa, n) { fori (i2_daa, m) { cout << (x)[i1_daa][i2_daa] << ' '; } cout << '\n'; } cout << endl
const ll MOD = 1000000007;
const ll INF = 2000000000;
const long long BIG = 1446803456761533460LL;
#define XL (x << 1)
#define XR (XL | 1)
#define MD ((l + r) >> 1)
#define Add(a, b) a = ((a) + (b)) % MOD
#define Mul(a, b) a = (1LL * (a) * (b)) % MOD
// -----------------------------------------------------------------------
const ll maxn = 100010;
const ll maxm = 300010;
const ll maxk = 20;
const ll maxv = maxk * 2;
ll N, M, K, P[maxn], E, cnte[maxn], V, ver[maxv], trans[maxn];
long long Ps[maxn];
pip es1[maxm], es2[maxv];
pii esk[maxk];
vpii tree[maxv];
struct DSU {
ll par[maxn];
void init(ll n) {
iota(par, par + n, 0);
}
ll root(ll x) {
return par[x] == x ? x : par[x] = root(par[x]);
}
} dsu1, dsu2, dsu3;
void compress_mst() {
fori (i, K) ++cnte[esk[i].F], ++cnte[esk[i].S];
sort(es1, es1 + M);
dsu1.init(N);
dsu2.init(N); // has more edges
fori (i, M) {
auto [a, b] = es1[i].S;
a = dsu1.root(a), b = dsu2.root(b);
if (a != b) {
if (cnte[b] > 0) swap(a, b);
if (cnte[b] > 0) {
ll r2a = dsu2.root(a), r2b = dsu2.root(b);
if (r2a != r2b) {
es2[E++] = es1[i];
dsu2.par[r2b] = r2a;
}
} else {
dsu1.par[b] = a;
dsu2.par[b] = a;
P[a] += P[b];
}
}
}
fori (i, N) {
if (dsu1.root(i) == i) {
trans[i] = V;
ver[V++] = i;
}
}
}
bool dfs2(ll x, ll par, ll trg, ll wt) {
if (x == trg) return true;
fori (i, tree[x].size()) {
ll y = tree[x][i].F;
if (y != par) {
if (dfs2(y, x, trg, wt)) {
if (tree[x][i].S == -1) tree[x][i].S = wt;
return true;
}
}
}
return false;
}
bool make_mstk(ll b) {
dsu3.init(V);
fori (i, K) {
if (b >> i & 1) {
auto [a, b] = esk[i];
a = trans[a], b = trans[b];
ll ra = dsu3.root(a), rb = dsu3.root(b);
if (ra == rb) return false;
dsu3.par[ra] = rb;
tree[a].eb(b, -1), tree[b].eb(a, -1);
}
}
fori (i, E) {
auto [a, b] = es2[i].S;
a = trans[dsu1.root(a)], b = trans[dsu1.root(b)];
ll ra = dsu3.root(a), rb = dsu3.root(b);
if (ra != rb) {
dsu3.par[ra] = rb;
tree[a].eb(b, 0), tree[b].eb(a, 0);
} else {
dfs2(a, -1, b, es2[i].F);
}
}
return true;
}
long long dfs(ll x, ll par) {
long long s = 0;
Ps[x] = P[ver[x]];
for (auto [y, w] : tree[x]) if (y != par) {
s += dfs(y, x);
s += Ps[y] * w;
Ps[x] += Ps[y];
}
return s;
}
long long fix_k() {
ll rot = trans[dsu1.root(0)];
long long mx = 0;
fori (b, 1 << K) {
fori (i, V) tree[i].clear();
if (make_mstk(b)) {
long long v = dfs(rot, -1);
smax(mx, v);
}
}
return mx;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> N >> M >> K;
fori (i, M) {
ll a, b, c; cin >> a >> b >> c; --a, --b;
es1[i] = {c, {a, b}};
}
fori (i, K) {
ll a, b; cin >> a >> b; --a, --b;
esk[i] = {a, b};
}
fori (i, N) cin >> P[i];
compress_mst();
long long ans = fix_k();
cout << ans << '\n';
}
Compilation message
toll.cpp: In function 'bool dfs2(ll, ll, ll, ll)':
toll.cpp:26:44: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | #define forifrom(i, s, n) for (ll i = s; i < n; ++i)
| ^
toll.cpp:28:20: note: in expansion of macro 'forifrom'
28 | #define fori(i, n) forifrom (i, 0, n)
| ^~~~~~~~
toll.cpp:112:5: note: in expansion of macro 'fori'
112 | fori (i, tree[x].size()) {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
