Submission #287591

#TimeUsernameProblemLanguageResultExecution timeMemory
287591NamnamseoToll (APIO13_toll)C++17
0 / 100
2 ms2940 KiB
#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 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]; } 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){ 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=0; 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; ret += yd(gy, y); if (isk) ret += S[gy] * (dist(j, h)+d); S[x] += S[y]; } V[x]=0; 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; 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 (stderr)

toll.cpp: In function 'int main()':
toll.cpp:166:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  166 |  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);
      |  ^~~
toll.cpp:166:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  166 |  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);
      |                                               ^~~~~~~
toll.cpp:166:77: warning: ignoring return value of 'ssize_t write(int, const void*, size_t)', declared with attribute warn_unused_result [-Wunused-result]
  166 |  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);
      |                                                                        ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...