| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 355162 |
2021-01-22T09:39:34 Z |
songc |
Toll (APIO13_toll) |
C++14 |
|
2500 ms |
19948 KB |
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define Mup(a,x) a=max(a, x)
#define mup(a,x) a=min(a, x)
#define all(v) v.begin(),v.end()
#define lb lower_bound
#define INF (1ll<<60)
#define MOD 1'000'000'007
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
int N, M, K, bi;
int P[101010], U[30], V[30];
LL A[101010], ans, sum;
vector<pii> adj[101010];
bool chk[101010];
int rt(int u){
if (u == P[u]) return u;
return P[u] = rt(P[u]);
}
struct Edge{
LL u, v, w;
} edg[303030];
vector<Edge> E[101010];
int dfs1(int u, int p){
int cnt=0;
for (pii v : adj[u]){
if (v.fi == p) continue;
int p = dfs1(v.fi, u);
if (!p) A[u] += A[v.fi];
cnt += p;
}
if (cnt >= 2) chk[u] = true;
if (cnt || chk[u]) return 1;
return 0;
}
void dfs2(int u, int p, int pp, int mx, LL ps, LL s){
if (chk[u]){
if (u>1){
E[pp].pb((Edge){u, ps, mx});
E[u].pb((Edge){pp, s-ps, mx});
}
pp=u, mx=0, ps=0, s=-A[u];
}
for (pii v : adj[u]){
if (v.fi == p) continue;
if (mx < v.se) dfs2(v.fi, u, pp, v.se, s+A[u], s+A[u]);
else dfs2(v.fi, u, pp, mx, ps, s+A[u]);
}
}
pii path(int u, int p, int t, int mx, pii r){
if (u == t) return r;
for (int i=0; i<E[u].size(); i++){
if (E[u][i].u == p) continue;
pii ret = pii(0,0);
if (E[u][i].w > mx && E[u][i].v != -1) ret = path(E[u][i].u, u, t, E[u][i].w, pii(u, E[u][i].u));
else ret = path(E[u][i].u, u, t, mx, r);
if (ret != pii(0,0)) return ret;
}
return pii(0, 0);
}
bool upd(int u, int p, int t, int x, vector<Edge> &rb){
if (u == t) return true;
for (int i=0; i<E[u].size(); i++){
if (E[u][i].u == p) continue;
if (upd(E[u][i].u, u, t, x, rb)){
if (E[u][i].v < 0 && E[u][i].w > x){
rb.pb((Edge){u, E[u][i].u, E[u][i].w});
E[u][i].w = x;
}
return true;
}
}
return false;
}
LL calc(int u, int p){
LL w = A[u];
for (int i=0; i<E[u].size(); i++){
if (E[u][i].u == p){
if (E[u][i].v != -1) w += E[u][i].v;
continue;
}
LL r = calc(E[u][i].u, u);
if (E[u][i].v < 0) sum += E[u][i].w * r;
else r += E[u][i].v;
w += r;
}
return w;
}
Edge del(int u, int v){
Edge ret;
for (int i=0; i<E[u].size(); i++) if (E[u][i].u == v){
ret = E[u][i];
swap(E[u][i], E[u].back());
E[u].pop_back();
}
return ret;
}
void bt(int k){
if (k > K){
sum = 0, calc(1, 0);
ans = max(ans, sum);
return;
}
bi <<= 1;
bt(k+1);
bi >>= 1;
int u, v;
tie(u, v) = path(U[k], 0, V[k], 0, pii(0,0));
if (!u) return;
Edge eu = del(u, v), ev = del(v, u);
A[u] += eu.v, A[v] += ev.v;
E[U[k]].pb((Edge){V[k], -1, eu.w});
E[V[k]].pb((Edge){U[k], -1, eu.w});
vector<Edge> rb;
upd(u, 0, v, eu.w, rb);
upd(v, 0, u, eu.w, rb);
bi <<= 1;
bi += 1;
bt(k+1);
bi >>= 1;
for (Edge it : rb){
del(it.u, it.v), del(it.v, it.u);
E[it.u].pb((Edge){it.v, -1, it.w});
E[it.v].pb((Edge){it.u, -1, it.w});
}
rb.clear();
del(U[k], V[k]), del(V[k], U[k]);
E[u].pb(eu), E[v].pb(ev);
A[u] -= eu.v, A[v] -= ev.v;
}
int main(){
scanf("%d %d %d", &N, &M, &K);
for (int i=1; i<=M; i++) scanf("%lld %lld %lld", &edg[i].u, &edg[i].v, &edg[i].w);
for (int i=1; i<=N; i++) P[i] = i;
sort(edg+1, edg+M+1, [&](Edge a, Edge b){return a.w < b.w;});
for (int i=1; i<=M; i++){
if (rt(edg[i].u) == rt(edg[i].v)) continue;
P[rt(edg[i].u)] = rt(edg[i].v);
adj[edg[i].u].pb(pii(edg[i].v, edg[i].w));
adj[edg[i].v].pb(pii(edg[i].u, edg[i].w));
}
chk[1] = true;
for (int i=1; i<=K; i++){
scanf("%d %d", &U[i], &V[i]);
chk[U[i]] = chk[V[i]] = true;
}
for (int i=1; i<=N; i++) scanf("%lld", &A[i]);
dfs1(1, 0);
dfs2(1, 0, 0, 0, 0, 0);
bt(1);
printf("%lld\n", ans);
return 0;
}
Compilation message
toll.cpp: In function 'pii path(int, int, int, int, pii)':
toll.cpp:61:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for (int i=0; i<E[u].size(); i++){
| ~^~~~~~~~~~~~
toll.cpp: In function 'bool upd(int, int, int, int, std::vector<Edge>&)':
toll.cpp:73:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int i=0; i<E[u].size(); i++){
| ~^~~~~~~~~~~~
toll.cpp: In function 'LL calc(int, int)':
toll.cpp:88:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for (int i=0; i<E[u].size(); i++){
| ~^~~~~~~~~~~~
toll.cpp: In function 'Edge del(int, int)':
toll.cpp:103:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for (int i=0; i<E[u].size(); i++) if (E[u][i].u == v){
| ~^~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:149:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
149 | scanf("%d %d %d", &N, &M, &K);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:150:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
150 | for (int i=1; i<=M; i++) scanf("%lld %lld %lld", &edg[i].u, &edg[i].v, &edg[i].w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:161:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
161 | scanf("%d %d", &U[i], &V[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:164:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
164 | for (int i=1; i<=N; i++) scanf("%lld", &A[i]);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 5 |
Correct |
9 ms |
5356 KB |
Output is correct |
| 6 |
Correct |
8 ms |
5356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 5 |
Correct |
9 ms |
5356 KB |
Output is correct |
| 6 |
Correct |
8 ms |
5356 KB |
Output is correct |
| 7 |
Correct |
298 ms |
18796 KB |
Output is correct |
| 8 |
Correct |
273 ms |
19948 KB |
Output is correct |
| 9 |
Correct |
266 ms |
19820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 5 |
Correct |
9 ms |
5356 KB |
Output is correct |
| 6 |
Correct |
8 ms |
5356 KB |
Output is correct |
| 7 |
Correct |
298 ms |
18796 KB |
Output is correct |
| 8 |
Correct |
273 ms |
19948 KB |
Output is correct |
| 9 |
Correct |
266 ms |
19820 KB |
Output is correct |
| 10 |
Execution timed out |
2558 ms |
19780 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
