| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 159481 |
2019-10-22T23:25:40 Z |
combi1k1 |
Toll (APIO13_toll) |
C++14 |
|
7 ms |
5112 KB |
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
#define ll long long
#define ed tuple<int,int,int>
#define FOR(i,a,b) for(int i = a ; i < b ; ++i)
const int N = 1e5 + 5;
namespace DSU {
int p[N];
int s[N];
int init(int n) {
iota(p + 1,p + 1 + n,1);
fill(s + 1,s + 1 + n,1);
return 1;
}
int lead(int x) {
return p[x] == x ? x : p[x] = lead(p[x]);
}
int join(int x,int y) {
x = lead(x);
y = lead(y);
if (x == y) return 0;
if (s[x] < s[y])
swap(x,y);
p[y] = x;
s[x] += s[y];
return 1;
}
};
typedef pair<int,int> ii;
vector<ii> g1[N];
vector<ii> g2[N];
vector<ed> rem;
int x[N], y[N];
ll a[N], f[N];
int dep[N];
int idx[N], tot = 0;
ll nCh[N], ans = 0;
ii anc[N];
int lim[N];
int ini(int u,int p) {
idx[u] = tot;
f[tot] += a[u];
for(ii e : g1[u]) if (e.X != p)
ini(e.X,u);
}
int dfs(int u,int p) {
nCh[u] = f[u];
for(ii e : g2[u]) {
if (e.X == p) anc[u] = e;
else
dep[e.X] = dep[u] + 1,
dfs(e.X,u),
nCh[u] += nCh[e.X];
}
}
void goUp(int &u,int w) {
if (anc[u].Y) lim[anc[u].Y] = min(lim[anc[u].Y],w);
u = anc[u].X;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
int m; cin >> m;
int k; cin >> k;
vector<ed> E;
FOR(i,0,m) {
int u; cin >> u;
int v; cin >> v;
int w; cin >> w;
E.pb(make_tuple(w,u,v));
}
sort(E.begin(),E.end()); DSU::init(n);
FOR(i,0,m) {
int w, u, v;
tie(w, u, v) = E[i];
if (DSU::join(u,v))
E.pb(E[i]);
}
reverse(E.begin(),E.end()); E.resize(n - 1);
reverse(E.begin(),E.end()); DSU::init(n);
FOR(i,0,k) {
cin >> x[i] >> y[i];
DSU::join(x[i],y[i]);
}
FOR(i,1,n) {
int w, u, v;
tie(w, u, v) = E[i - 1];
if (DSU::join(u,v))
g1[u].pb({v,w}),
g1[v].pb({u,w});
else
rem.pb(E[i - 1]);
}
FOR(i,0,n) cin >> a[i + 1];
FOR(i,1,n + 1) if(!idx[i]) {
tot++;
ini(i,0);
}
FOR(m,0,1 << k) {
FOR(i,1,tot + 1)
DSU::p[i] = i,
DSU::s[i] = 1,
g2[i].clear(),
lim[i] = 1e9;
int Cyc = 0;
ll res = 0;
FOR(i,0,k) if (m >> i & 1) {
int u = idx[x[i]];
int v = idx[y[i]];
if (DSU::join(u,v))
g2[u].pb({v,i + 1}),
g2[v].pb({u,i + 1});
else Cyc = 0;
}
if (Cyc) continue;
vector<ed> tmp;
for(ed e : rem) {
int w, u, v;
tie(w, u, v) = e;
u = idx[u];
v = idx[v];
if (DSU::join(u,v))
g2[u].pb({v,0}),
g2[v].pb({u,0});
else tmp.pb(e);
}
dfs(1,0);
for(ed e : tmp) {
int w, u, v;
tie(w, u, v) = e;
u = idx[u];
v = idx[v];
if (dep[u] < dep[v])
swap(u,v);
while (dep[u] > dep[v])
goUp(u,w);
while (u != v)
goUp(u,w),
goUp(v,w);
}
FOR(i,0,k) if (m >> i & 1) {
int u = idx[x[i]];
int v = idx[y[i]];
if (dep[u] > dep[v])
swap(u,v);
res += nCh[v] * lim[i + 1];
}
ans = max(ans,res);
}
cout << ans << endl;
}
/*
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
*/
Compilation message
toll.cpp: In function 'int ini(int, int)':
toll.cpp:57:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
toll.cpp: In function 'int dfs(int, int)':
toll.cpp:67:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
7 ms |
5112 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
7 ms |
5112 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
7 ms |
5112 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
7 ms |
5112 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
