| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 287601 |
2020-08-31T20:59:36 Z |
Namnamseo |
Toll (APIO13_toll) |
C++17 |
|
6 ms |
5504 KB |
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/mman.h>
#include <unistd.h>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <cstdio>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=1;i<=n;++i)
#define pb push_back
#define eb emplace_back
#define printf if(0) printf
int n, m, k;
char *I;
int ri() { int ret=0; while (*I<48||*I>=58) ++I; while(*I>=48&&*I<58) ret=ret*10+(*(I++)-48); return ret; }
char Y[20];
struct E { int a, b, c; bool operator<(const E& r)const{ return c<r.c; } } e0[300010], ek[20], eu[300010], et[500]; int eun, etn;
struct UF { int p[100010]; void init(int s=n){iota(p+1,p+s+1,1);} int r(int x){return x==p[x]?x:(p[x]=r(p[x])); }
int join(int a,int b){ a=r(a);b=r(b); if(a==b) return 0;p[a]=b;return 1; }} uf, uf2, ufk;
int q[300010];
ll A;
int g[100010],r[100010],gn;
ll u[100010];
E md[50][50];
using pp=pair<int,int>;
vector<E> G[50];
vector<pp> T[100010];
int D[100010], P[20][100010];
ll F[100010];
ll s[100010];
ll dfs(int x){
ll ret=u[x]*F[x];
s[x]=u[x];
for(auto [y,d]:T[x]) if(P[0][x]!=y) {
D[y]=D[x]+1;
F[y]=F[x]+d;
P[0][y]=x;
ret+=dfs(y);
s[x]+=s[y];
}
printf("x=%d, par=%d, ret=%lld, s=%lld\n",
x, P[0][x], ret, s[x]);
return ret;
}
int lca(int a,int b){
if(D[a]>D[b])swap(a,b);
for(int df=D[b]-D[a],i=19;0<=i;--i)if(1&(df>>i))b=P[i][b];
if(a==b)return a;
for(int i=19;0<=i;--i)if(P[i][a]!=P[i][b])a=P[i][a],b=P[i][b];
return P[0][a];
}
ll dist(int a,int b){return F[a]+F[b]-2*F[lca(a,b)];}
ll C[100010];int L;
void l(int x){
printf("l(%d): C=%lld\n", x, C[x]);
for(auto[y,d]:T[x]) {
if(P[0][y]==x) {
C[y]=C[x]-d*1ll*s[y]+d*1ll*(L-s[y]);
l(y);
}
}
}
bool V[50]; ll S[50];
ll yd(int x, int j){
V[x]=1;
//ll ret=C[j];
ll ret=0;
printf("At j=%d, sum of dist = %lld\n", j, ret);
S[x]=s[r[x]];
for(auto&z:G[x]){
int y = z.a, gy = g[y], h = z.b, d = z.c;
bool isk = 0;
if (d < 0) isk = 1, d=-d;
if (V[gy]) continue;
printf("Children group %d, vertex %d->%d, dist=%d, isk=%d\n",
gy, h, y, d, isk);
ret += yd(gy, y);
if (isk) {
//ret += S[gy] * (dist(j, h)+d);
ret += S[gy] * d;
printf("S[gy]=%lld, dist=%lld, d=%d\n",
S[gy], dist(j, h), d);
}
S[x] += S[y];
}
V[x]=0;
printf("At j=%d, final ret = %lld\n", j, ret);
return ret;
}
void ae(int a, int b, int c) {
G[g[a]].pb({b, a, c});
G[g[b]].pb({a, b, c});
}
int main() {
setbuf(stdout, 0);
{ static char buf[100]; using Z=struct stat*; fstat(0, (Z)buf); I=(char*)mmap(0,Z(buf)->st_size,1,2,0,0);}
n = ri(); m = ri(); k = ri();
rep(i,m) e0[i].a=ri(), e0[i].b=ri(), e0[i].c=ri();
rep(i,k) ek[i].a=ri(), ek[i].b=ri();
rrep(i,n) u[i]=ri();
uf.init(); uf2.init(); rep(i,k) uf.join(ek[i].a,ek[i].b);
iota(q,q+m,0); sort(q,q+m,[&](const int&a,const int&b){ return e0[a]<e0[b]; });
rep(i,m) {
auto&e=e0[q[i]];
if (uf.join(e.a, e.b)) {
uf2.join(e.a, e.b);
T[e.a].eb(e.b, e.c);
T[e.b].eb(e.a, e.c);
} else {
eu[eun++]=e;
}
}
rrep(i,n) if (uf2.p[i]==i) r[g[i]=++gn]=i;
rrep(i,n) if (uf2.p[i]!=i) g[i]=g[uf2.r(i)];
memset(md,0x7f,sizeof(md));
rep(i,eun){
int a=g[eu[i].a], b=g[eu[i].b];
if (a != b) md[b][a]=md[a][b]=min(md[a][b], eu[i]);
}
rrep(i, gn) C[r[i]] = dfs(r[i]);
rrep(i, 19) rrep(j, n) P[i][j]=P[i-1][P[i-1][j]];
rrep(i, gn) L = s[r[i]], l(r[i]);
ll O = 0;
rep(m,(1<<k)) {
ufk.init(gn);
bool mf=0;
rep(j,k) if (1&(m>>j)) {
auto &e = ek[j];
int a=e.a, b=e.b;
if(g[a]==g[b] || !ufk.join(g[a],g[b])){ mf=1; break; }
}
if (mf) continue;
printf("Non-malformed trial %d\n", m);
rep(j,k) if (1&(m>>j)){
auto &e = ek[j]; ae(e.a, e.b, -md[g[e.a]][g[e.b]].c);
}
etn=0;
rrep(x, gn) rrep(y, x-1) if(ufk.r(x) != ufk.r(y))
et[etn++] = md[x][y];
sort(et,et+etn);
rep(j, etn){
int a=et[j].a, b=et[j].b, c=et[j].c;
if(ufk.join(a, b)) ae(a, b, c);
}
O=max(O, yd(g[1], 1));
rrep(x, gn) G[x].clear();
}
for(gn=0,O+=A;!gn||O;)Y[gn++]=48+O%10, O/=10;
reverse(Y,Y+gn); Y[gn]=10; write(1,Y,gn+1);
return 0;
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:183:34: warning: ignoring return value of 'ssize_t write(int, const void*, size_t)', declared with attribute warn_unused_result [-Wunused-result]
183 | reverse(Y,Y+gn); Y[gn]=10; write(1,Y,gn+1);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2816 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2816 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2816 KB |
Output is correct |
| 3 |
Runtime error |
6 ms |
5504 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2816 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2816 KB |
Output is correct |
| 3 |
Runtime error |
6 ms |
5504 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2816 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2816 KB |
Output is correct |
| 3 |
Runtime error |
6 ms |
5504 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2816 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2816 KB |
Output is correct |
| 3 |
Runtime error |
6 ms |
5504 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
