제출 #852465

#제출 시각아이디문제언어결과실행 시간메모리
852465midi꿈 (IOI13_dreaming)C++14
40 / 100
115 ms65536 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; #define vc vector typedef vc<ll> vcll; #define pr pair typedef pr<ll, ll> prll; #define umap unordered_map #define f0r(i,a,n) for (i=(a); i<(n); i++) #define f1r(i,a,n) for (i=(a); i<=(n); i++) #define r0f(i,n,a) for (i=(n); i>(a); i--) #define r1f(i,n,a) for (i=(n); i>=(a); i--) #define fi first #define se second #define pb push_back #define mp make_pair #define in(s, x) ((s).find((x)) != (s).end()) #define all(x) (x).begin(), (x).end() #define allrev(x) (x).rbegin(), (x).rend() inline void maxa(ll &a, ll b) { if (a<b) a=b; } inline void mina(ll &a, ll b) { if (a>b) a=b; } #define INF (LLONG_MAX>>2ll) #define mxN 100'010ll ll n, m, l; int *uar, *var, *war; vc<vc<prll>> gr(mxN); // fi is w, se is v vc<prll> par(mxN); vc<vcll> from_tar(mxN); // .back() is for the parent vc<umap<ll, ll>> nindex(mxN); // index of node in the gr, from_tar, excetera vcll f; inline void build_gr() { ll i; f0r(i,0,m) { ll u, v, w; u=uar[i]; v=var[i]; w=war[i]; nindex[u][v] = gr[u].size(); nindex[v][u] = gr[v].size(); gr[u].pb({w, v}); gr[v].pb({w, u}); from_tar[u].pb(-1); from_tar[v].pb(-1); } } vc<bool> seen(mxN, 0); vcll whole(mxN); // whole vcll comp; // comp for component void dfs(ll u) // makes tree // good { if (seen[u]) return; seen[u]=1; comp.pb(u); for (prll edge : gr[u]) { ll v=edge.se; if (seen[v]) continue; // is par ll w=edge.fi; par[v]={w, u}; dfs(v); } } ll calc_cnt=0; ll clutch_cnt=0; ll calc_whole(ll u) { ll m=0; // max for (prll edge : gr[u]) { ll v=edge.se; ll w = edge.fi; maxa(m, calc_whole(v) + w); } return whole[u]=m; } vc<umap<ll, ll>> max_except(mxN); void build_except(ll u, vc<prll> &ar) // fi is node, se is max { ll i; ll n=ar.size(); /* printf("bulid_except of u: %lli\n", u); printf("ar: "); f0r(i,0,n) printf("{%lli, %lli} ", ar[i].se, ar[i].fi); printf("\n"); */ vcll sma(n+10); // max, incl., sma[n]==0 sma[n]=0; r1f(i,n-1, 0) sma[i]=max(sma[i+1], ar[i].fi); /* printf("sma: "); f0r(i,0,n) printf("%lli ", sma[i]); printf("\n"); */ ll rm=0; // running max f0r(i,0,n) { max_except[u][ar[i].se] = max(rm, sma[i+1]); // printf("rm: %lli\n", rm); // printf("value of %lli: %lli\n", ar[i].se, max(rm, sma[i+1])); maxa(rm, ar[i].fi); } sma.clear(); } void build_ar_root(ll u) { vc<prll> ar; for (prll edge : gr[u]) { ll v=edge.se; ll w=edge.fi; ar.pb({whole[v]+w, v}); } build_except(u, ar); ar.clear(); } ll root; ll gm; ll dfs_calc_real(ll u) { ll m=whole[u]; // max if (u==root) { for (prll edge : gr[u]) { ll v = edge.se; mina(gm, dfs_calc_real(v)); } return m; } // u!=root vc<prll> ar; for (prll edge : gr[u]) { ll v = edge.se; ll w = edge.fi; ar.pb({whole[v]+w, v}); } ll p=par[u].se; ll w=par[u].fi; ll v = max_except[p][u]; maxa(whole[u], w+v); ar.pb({w+v, p}); m=whole[u]; build_except(u, ar); ar.clear(); for (prll edge : gr[u]) { ll v = edge.se; mina(gm, dfs_calc_real(v)); } return m; } inline void remake_gr() { for (ll u : comp) for (prll &edge : gr[u]) { ll v=edge.se; if (par[u].se==v) { edge=gr[u][gr[u].size()-1]; gr[u].pop_back(); } } } inline ll minmaxdist(ll u) { comp.clear(); root=u; par[root]={0, -1}; dfs(u); // good remake_gr(); // bad // printf("comp.size: %lli\n", (ll)comp.size()); calc_whole(u); // prob works build_ar_root(u); gm=INF; ll t = dfs_calc_real(u); // min mina(gm, t); // printf("m: %lli, on u: %lli\n", m, u); return gm; } inline void build_ar() { ll u; f0r(u,0,n) { if (seen[u]) continue; // printf("WPAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA, u: %lli\n", u); f.pb(minmaxdist(u)); } } inline ll value() { ll z=f.size(); ll m=-1; // max /* printf("z: %lli\n", z); printf("f: "); for (ll v : f) printf("%lli ", v); printf("\n"); */ if (z==1) m = f[0]; else if (z==2) m = f[0]+f[1]+l; else m = max(f[0]+f[1]+l, f[1]+f[2]+(2*l)); ll u; f0r(u,0,n) maxa(m, whole[u]); return m; } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { n=N; m=M; l=L; uar=A; var=B; war=T; build_gr(); build_ar(); // slow sort(allrev(f)); return value(); }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...