| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 39133 |
2018-01-09T13:18:17 Z |
qoo2p5 |
Toll (APIO13_toll) |
C++14 |
|
9 ms |
2812 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;
const ld EPS = (ld) 1e-7;
const ll MOD = (ll) 1e9 + 7;
#define sz(x) (int) (x).size()
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb(s, t, x) (int) (lower_bound(s, t, x) - s)
#define ub(s, t, x) (int) (upper_bound(s, t, x) - s)
#define rep(i, f, t) for (int i = f; i < t; i++)
#define per(i, f, t) for (int i = f; i >= t; i--)
ll power(ll x, ll y, ll mod = MOD) {
if (y == 0) {
return 1;
}
if (y & 1) {
return power(x, y - 1, mod) * x % mod;
} else {
ll tmp = power(x, y / 2, mod);
return tmp * tmp % mod;
}
}
template<typename A, typename B> bool mini(A &x, const B &y) {
if (y < x) {
x = y;
return true;
}
return false;
}
template<typename A, typename B> bool maxi(A &x, const B &y) {
if (y > x) {
x = y;
return true;
}
return false;
}
void add(ll &x, ll y) {
x += y;
if (x >= MOD) x -= MOD;
if (x < 0) x += MOD;
}
ll mult(ll x, ll y) {
return x * y % MOD;
}
void run();
#define TASK ""
int main() {
#ifdef LOCAL
if (strlen(TASK) > 0) {
cerr << "Reminder: you are using file i/o, filename: " TASK "!" << endl << endl;
}
#endif
#ifndef LOCAL
if (strlen(TASK)) {
freopen(TASK ".in", "r", stdin);
freopen(TASK ".out", "w", stdout);
}
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#endif
cout << fixed << setprecision(12);
run();
return 0;
}
// == SOLUTION == //
const int N = 5005;
const int L = 13;
struct Edge {
int u, v, c;
bool operator<(const Edge &e) const {
return c < e.c;
}
};
int n, m, k;
int amount[N];
Edge e[N], my[N];
int p[N];
vector<pair<int, int>> g[N];
int get(int v) {
return (p[v] == v ? v : (p[v] = get(p[v])));
}
bool unite(int u, int v) {
u = get(u);
v = get(v);
if (u == v) {
return 0;
}
p[u] = v;
return 1;
}
void clr() {
rep(i, 0, n + 1) {
p[i] = i;
g[i].clear();
}
}
int depth[N];
int up[N][L];
int tin[N], tout[N];
int tmr;
void calc_up(int v, int f = -1) {
if (f == -1) {
tmr = 0;
fill(up[v], up[v] + L, v);
depth[v] = 0;
} else {
up[v][0] = f;
rep(i, 1, L) {
up[v][i] = up[up[v][i - 1]][i - 1];
}
}
tin[v] = tmr++;
for (auto &e : g[v]) {
int u = e.first;
if (u == f) {
continue;
}
depth[u] = depth[v] + 1;
calc_up(u, v);
}
tout[v] = tmr - 1;
}
int go(int v, int h) {
rep(i, 0, L) {
if (h & (1 << i)) {
v = up[v][i];
}
}
return v;
}
int lca(int u, int v) {
if (depth[u] < depth[v]) {
swap(u, v);
}
u = go(u, depth[u] - depth[v]);
per(i, L - 1, 0) {
int uu = up[u][i];
int vv = up[v][i];
if (uu != vv) {
u = uu;
v = vv;
}
}
return up[u][0];
}
bool check_st(int st, int v) {
return tin[st] <= tin[v] && tout[v] <= tout[st];
}
bool check_path(int u, int v, int w, int a, int b) {
if (depth[a] < depth[b]) {
swap(a, b);
}
return !check_st(a, w) && (check_st(a, u) || check_st(a, v));
}
bool taken[N];
ll mi[N];
vector<pair<ll, ll>> opt;
ll dfs(int v, int f = -1) {
ll res = amount[v];
for (auto &e : g[v]) {
int u = e.first;
if (u == f) {
continue;
}
int id = e.second;
ll t = dfs(u, v);
if (id >= 0) {
opt.pb({t, mi[id]});
}
res += t;
}
return res;
}
bool mark(int v, int dest, int w, int f = -1) {
if (v == dest) {
return 1;
}
for (auto &it : g[v]) {
int u = it.first;
int id = it.second;
if (u == f) {
continue;
}
if (mark(u, dest, w, v)) {
if (id >= 0) {
mini(mi[id], w);
}
return 1;
}
}
return 0;
}
void run() {
cin >> n >> m >> k;
rep(i, 0, m) {
cin >> e[i].u >> e[i].v >> e[i].c;
}
sort(e, e + m);
rep(i, 0, k) {
cin >> my[i].u >> my[i].v;
}
rep(i, 1, n + 1) {
cin >> amount[i];
}
ll init = 0;
{
clr();
rep(i, 0, m) {
init += e[i].c * unite(e[i].u, e[i].v);
}
}
ll ans = 0;
rep(mask, 1, 1 << k) {
clr();
bool ok = 1;
int cnt = 0;
rep(i, 0, k) {
if (mask & (1 << i)) {
ok &= unite(my[i].u, my[i].v);
g[my[i].u].pb({my[i].v, i});
g[my[i].v].pb({my[i].u, i});
cnt++;
}
}
if (!ok) {
continue;
}
ll rest = init;
memset(taken, 0, sizeof taken);
rep(i, 0, m) {
if (unite(e[i].u, e[i].v)) {
rest -= e[i].c;
g[e[i].u].pb({e[i].v, -1});
g[e[i].v].pb({e[i].u, -1});
taken[i] = 1;
}
}
fill(mi, mi + k, LINF);
calc_up(1);
rep(i, 0, m) {
if (!taken[i]) {
int u = e[i].u;
int v = e[i].v;
int w = lca(u, v);
rep(j, 0, k) {
if (!(mask & (1 << j))) {
continue;
}
int a = my[j].u;
int b = my[j].v;
assert(abs(depth[a] - depth[b]) == 1);
if (check_path(u, v, w, a, b)) {
mini(mi[j], e[i].c);
}
}
}
}
/*rep(i, 0, m) { SLOW
if (!taken[i]) {
mark(e[i].u, e[i].v, e[i].c);
}
}*/
opt.clear();
dfs(1);
assert(sz(opt) == cnt);
sort(all(opt));
reverse(all(opt));
ll cur = 0;
for (auto &it : opt) {
ll cost = min(rest, it.second);
rest -= cost;
cur += cost * it.first;
}
maxi(ans, cur);
}
cout << ans << "\n";
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:72:40: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(TASK ".in", "r", stdin);
^
toll.cpp:73:42: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(TASK ".out", "w", stdout);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2812 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2812 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2812 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2812 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
2812 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2812 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2812 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
2812 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2812 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2812 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
2812 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2812 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2812 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
2812 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
