| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 50679 |
2018-06-12T14:13:52 Z |
ayhcbagnop |
Toll (APIO13_toll) |
C++14 |
|
3 ms |
376 KB |
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef vector<int> vi;
typedef long long ll;
const int maxn = 1e5+5;
const int maxk = 25;
struct edge
{
int u, v, w;
bool is_hard, in_mst;
edge(int _u, int _v, int _w)
{
u = _u; v = _v; w = _w;
is_hard = 0;
in_mst = 0;
}
bool operator < (edge other)
{
return w< other.w;
}
};
int n, m, k;
int size;
int par[maxn];
int sz[maxn];
int treecomp[maxn];
int treesz[maxn];
vi adj[maxk];
vi weight[maxk];
int dep[maxk];
int up[maxk];
int subsz[maxk];
int b4[maxk];
void setsz(int x)
{
size = x;
}
void reset()
{
for(int i = 1; i<= size; i++) par[i] = i;
}
int pong(int x)
{
if(par[x] == x) return x;
return par[x] = pong(par[x]);
}
void tfs(int u, int par)
{
subsz[u] = treesz[u];
for(int i = 0; i< (int) adj[u].size(); i++)
{
int v = adj[u][i], w = weight[u][i];
if(v == par) continue;
up[v] = w;
dep[v] = dep[u]+1;
b4[v] = u;
tfs(v, u);
subsz[u] += subsz[v];
}
}
int main()
{
scanf("%d %d %d", &n, &m, &k);
vector<edge> norm;
vector<edge> sp;
for(int i = 0; i< m; i++)
{
int u, v, w; scanf("%d %d %d", &u, &v, &w);
norm.pb(edge(u, v, w));
}
for(int i = 0; i< k; i++)
{
int u, v; scanf("%d %d", &u, &v);
sp.pb(edge(u, v, 0));
}
for(int i = 1; i<= n; i++) scanf("%d", &sz[i]);
sort(norm.begin(), norm.end());
setsz(n);
reset();
for(int i = 0; i< m; i++)
{
int a = pong(norm[i].u), b = pong(norm[i].v);
if(a == b) continue;
par[a] = b; norm[i].in_mst = true;
//printf("%d %d is in mst\n", norm[i].u, norm[i].v);
}
reset();
for(int i = 0; i< k; i++)
{
int a = pong(sp[i].u), b = pong(sp[i].v);
//printf("connect %d %d\n", a, b);
par[a] = b;
}
for(int i = 0; i< m; i++)
{
int a = pong(norm[i].u), b = pong(norm[i].v);
if(a == b) continue;
par[a] = b;
//printf("%d %d is hard!\n", norm[i].u, norm[i].v);
norm[i].is_hard = true;
}
reset();
vector<edge> soft;
for(int i = 0; i< m; i++)
{
if(norm[i].is_hard)
{
int a = pong(norm[i].u), b = pong(norm[i].v);
par[a] = b;
}
}
int comps = 0;
for(int i = 1; i<= n; i++)
{
if(pong(i) == i)
{
comps++; treecomp[i] = comps;
}
}
for(int i = 1; i<= n; i++)
{
if(pong(i) != i)
{
treecomp[i] = treecomp[pong(i)];
}
}
for(int i = 1; i<= n; i++) treesz[treecomp[pong(i)]] += sz[i];
for(int i = 0; i< m; i++)
{
if(!norm[i].is_hard && norm[i].in_mst)
{
soft.pb(edge(treecomp[norm[i].u], treecomp[norm[i].v], norm[i].w));
}
}
ll best = 0;
for(int mask = 0; mask < (1<<k); mask++)
{
setsz(comps); reset();
bool is_cycle = false;
for(int i = 1; i<= comps; i++)
{
adj[i].clear(); weight[i].clear();
}
for(int i = 0; i< k; i++)
{
if((1<<i)&mask)
{
int a = pong(treecomp[sp[i].u]), b = pong(treecomp[sp[i].v]);
if(a == b)
{
is_cycle = true;
break;
}
par[a] = b;
adj[treecomp[sp[i].u]].pb(treecomp[sp[i].v]); weight[treecomp[sp[i].u]].pb(2e9);
adj[treecomp[sp[i].v]].pb(treecomp[sp[i].u]); weight[treecomp[sp[i].v]].pb(2e9);
}
}
if(is_cycle) continue;
vector<edge> gas;
for(int i = 0; i< (int) soft.size(); i++)
{
int a = pong(soft[i].u), b = pong(soft[i].v);
if(a == b) gas.pb(soft[i]);
else
{
par[a] = b;
adj[soft[i].u].pb(soft[i].v); weight[soft[i].u].pb(0);
adj[soft[i].v].pb(soft[i].u); weight[soft[i].v].pb(0);
}
}
dep[treecomp[1]] = 1; tfs(treecomp[1], 0);
for(int i = 0; i< (int) gas.size(); i++)
{
int u = gas[i].u, v = gas[i].v;
int w = gas[i].w;
if(dep[u]< dep[v]) swap(u, v);
while(dep[u]> dep[v])
{
up[u] = min(up[u], w);
u = b4[u];
}
while(u != v)
{
up[u] = min(up[u], w);
up[v] = min(up[v], w);
u = b4[u], v = b4[v];
}
}
ll here = 0;
for(int i = 2; i<= comps; i++) here += subsz[i]*up[i];
best = max(here, best);
}
printf("%lld\n", best);
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &m, &k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:69:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int u, v, w; scanf("%d %d %d", &u, &v, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:74:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int u, v; scanf("%d %d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~~
toll.cpp:77:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1; i<= n; i++) scanf("%d", &sz[i]);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
