Submission #1275497

#TimeUsernameProblemLanguageResultExecution timeMemory
1275497quanduongxuan12Dreaming (IOI13_dreaming)C++20
100 / 100
46 ms18656 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; #define name "dreaming" #define MAXN 100005 #define pb push_back #define pf push_front #define ll long long #define ii pair<int, int> #define fs first #define sc second #define ill pair<int, ll> #define lli pair<ll, int> #define llll pair<ll, ll> #define all(v) v.begin(),v.end() #define uni(v) v.erase(unique(all(v)),v.end()) #define bit(n,i) (((n)>>(i))&1) #define FOR(i,a,b) for (int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for (int i=(a),_b=(b); i>=_b; i--) #define MASK(i) (1LL<<(i)) const int INF=1e9; const int MOD=1e9+7; void add(int &u, int v){ u+=v; if (u>=MOD) u-=MOD; } void sub(int &u, int v){ u-=v; if (u<0) u+=MOD; } void minimize(int &u, int v){ u=min(u,v); } void maximize(int &u, int v){ u=max(u,v); } long long Rand(long long l, long long r){ ll tmp=0; FOR(i,1,4) tmp=((tmp<<15)^(((1<<15)-1)&rand())); return l+tmp%(r-l+1); } ii Max[MAXN],res[MAXN]; vector<ii> adj[MAXN]; int depth[MAXN],high[MAXN]; bool visited[MAXN]; vector<ii> vec; void dfs0(int u, int p){ visited[u]=1; Max[u]={0,0}; for (ii pairs:adj[u]){ int v=pairs.fs; int w=pairs.sc; if (v==p) continue; dfs0(v,u); maximize(high[u],high[v]+w); if (high[v]+w>Max[u].fs){ Max[u].sc=Max[u].fs; Max[u].fs=high[v]+w; } else maximize(Max[u].sc,high[v]+w); } } int diam; void dfs1(int u, int p){ res[u]=Max[u]; if (depth[u]>res[u].fs){ res[u].sc=res[u].fs; res[u].fs=depth[u]; } else maximize(res[u].sc,depth[u]); if (res[u].fs+res[u].sc>diam){ diam=res[u].fs+res[u].sc; vec.back()=res[u]; } else if (res[u].fs+res[u].sc==diam){ if (vec.back().fs>res[u].fs) vec.back()=res[u]; } for (ii pairs:adj[u]){ int v=pairs.fs; int w=pairs.sc; if (v==p) continue; if (Max[u].fs==Max[v].fs+w){ depth[v]=max(depth[u],Max[u].sc)+w; } else{ depth[v]=max(depth[u],Max[u].fs)+w; } dfs1(v,u); } } bool cmp(const ii& X, const ii& Y){ return X.fs>Y.fs; } int travelTime(int N, int M, int L, int A[], int B[], int T[]){ FOR(i,1,M){ int x=A[i-1],y=B[i-1],w=T[i-1]; ++x; ++y; adj[x].pb({y,w}); adj[y].pb({x,w}); } int kq=0; FOR(i,1,N) if (!visited[i]){ dfs0(i,0); diam=0; vec.pb({0,0}); dfs1(i,0); maximize(kq,diam); } sort(all(vec),cmp); if (vec.size()>=2) maximize(kq,vec[0].fs+vec[1].fs+L); if (vec.size()>=3) maximize(kq,vec[2].fs+vec[1].fs+2*L); return kq; }
#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...