| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 441681 |
2021-07-05T19:13:25 Z |
AriaH |
Toll (APIO13_toll) |
C++17 |
|
16 ms |
21452 KB |
/** work as hard as you can and keep the first place **/
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define Mp make_pair
const int N = 3e5 + 50;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const int LOG = 20;
ll pw(ll a, ll b, ll M = mod, ll ret = 1) { while(b) { ret = ret * (b & 1? a : 1) % M, a = a * a % M, b >>= 1; } return ret; }
ll tot, ret, ted[N], sub[N], Size[N];
int n, m, k, ptr, ROOT, V[N], U[N], C[N], par[N], ord[N], in1[N], in2[N], T[N], query[N], St[N], Fi[N];
vector < int > vec, roots, G[N];
inline void init() { for(int i = 1; i <= n; i ++) par[i] = i, ted[i] = T[i]; }
int get(int x) { return (x == par[x]? x : par[x] = get(par[x])); }
bool unify(int v, int u)
{
v = get(v), u = get(u);
if(v == u) return 0;
par[u] = v;
ted[v] += ted[u];
return 1;
}
bool cmp(int i, int j)
{
return C[i] < C[j];
}
set < pii > st[N];
void pre(int v, int last = 0)
{
St[v] = ++ptr;
for(auto id : G[v])
{
if(id == last) continue;
int u = V[id] ^ U[id] ^ v;
pre(u, id);
}
Fi[v] = ptr;
///printf("v = %d St = %d Fi = %d\n", v, St[v], Fi[v]);
}
void dfs(int v, int last = 0)
{
sub[v] = Size[v];
for(auto id : G[v])
{
if(id == last) continue;
int u = V[id] ^ U[id] ^ v;
dfs(u, id);
if(SZ(st[v]) < SZ(st[u])) st[v].swap(st[u]);
for(auto now : st[u])
{
int node = now.S;
if(!(St[v] <= St[node] && Fi[node] <= Fi[v]))
{
st[v].insert(now);
}
}
sub[v] += sub[u];
}
pii cu = *st[v].begin();
while(St[v] <= St[cu.S] && Fi[cu.S] <= Fi[v])
{
st[v].erase(cu);
cu = *st[v].begin();
}
if(last > m)
{
ret += cu.F * sub[v];
}
}
void solve(int mask)
{
///printf("mask = %d\n", mask);
ptr = 0;
ret = 0;
for(auto v : roots) G[v].clear(), par[v] = v, ted[v] = 0, st[v].clear();
for(int i = m + 1; i <= m + k; i ++)
{
int id = i - m - 1;
if(mask >> id & 1)
{
G[V[i]].push_back(i);
G[U[i]].push_back(i);
///printf("E = %d\n", i);
if(!unify(V[i], U[i])) return;
}
}
for(auto i : vec)
{
if(unify(V[i], U[i]))
{
G[V[i]].push_back(i);
G[U[i]].push_back(i);
///printf("E = %d\n", i);
}
else
{
st[V[i]].insert({C[i], U[i]});
st[U[i]].insert({C[i], V[i]});
}
}
pre(ROOT);
dfs(ROOT);
tot = max(tot, ret);
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= m; i ++)
{
scanf("%d%d%d", &V[i], &U[i], &C[i]);
ord[i] = i;
}
sort(ord + 1, ord + m + 1, cmp);
init();
for(int j = 1; j <= m; j ++)
{
int i = ord[j];
in1[i] = unify(V[i], U[i]);
}
init();
for(int i = m + 1; i <= m + k; i ++)
{
scanf("%d%d", &V[i], &U[i]);
unify(V[i], U[i]);
}
for(int i = 1; i <= n; i ++) { scanf("%d", &T[i]); }
for(int j = 1; j <= m; j ++)
{
int i = ord[j];
in2[i] = unify(V[i], U[i]);
}
init();
for(int i = 1; i <= m; i ++)
{
if(in1[i] > in2[i])
{
vec.push_back(i);
}
if(in2[i])
{
unify(V[i], U[i]);
}
}
for(int i = 1; i <= n; i ++)
{
roots.push_back(get(i));
}
sort(all(roots));
roots.resize(unique(all(roots)) - roots.begin());
for(auto v : roots)
{
Size[v] = ted[v];
}
for(int i = 1; i <= m + k; i ++)
{
V[i] = get(V[i]), U[i] = get(U[i]);
}
ROOT = get(1);
for(int mask = 0; mask < 1 << k; mask ++)
{
solve(mask);
}
printf("%lld\n", tot);
return 0;
}
/** test corner cases(n = 1?) watch for overflow or minus indices **/
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:134:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
134 | scanf("%d%d%d", &n, &m, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:137:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
137 | scanf("%d%d%d", &V[i], &U[i], &C[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:150:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
150 | scanf("%d%d", &V[i], &U[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:153:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
153 | for(int i = 1; i <= n; i ++) { scanf("%d", &T[i]); }
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
21452 KB |
Output is correct |
| 2 |
Correct |
14 ms |
21452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
21452 KB |
Output is correct |
| 2 |
Correct |
14 ms |
21452 KB |
Output is correct |
| 3 |
Incorrect |
16 ms |
21440 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
21452 KB |
Output is correct |
| 2 |
Correct |
14 ms |
21452 KB |
Output is correct |
| 3 |
Incorrect |
16 ms |
21440 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
21452 KB |
Output is correct |
| 2 |
Correct |
14 ms |
21452 KB |
Output is correct |
| 3 |
Incorrect |
16 ms |
21440 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
21452 KB |
Output is correct |
| 2 |
Correct |
14 ms |
21452 KB |
Output is correct |
| 3 |
Incorrect |
16 ms |
21440 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
