Submission #1267477

#TimeUsernameProblemLanguageResultExecution timeMemory
1267477WH8Dreaming (IOI13_dreaming)C++20
100 / 100
51 ms19648 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; using ll=long long; vector<vector<pair<int, ll>>> al(100005); vector<tuple<ll, int, ll>> dist(100005, {1e12, -1, 0}); // dist, previous node, previous edge weight vector<int> curtree; vector<ll> guys; vector<bool> vis(100005); void dfs(int cur, pair<int,ll> pre){ curtree.push_back(cur); for(auto [to, cost]:al[cur]){ //~ printf("at %d, to %d, cost %d\n", cur, to, cost); if(to==pre.first)continue; get<0>(dist[to])=get<0>(dist[cur])+cost; get<1>(dist[to])=cur; get<2>(dist[to])=cost; dfs(to, {cur, cost}); } } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { for(int i=0;i<M;i++){ al[A[i]].push_back({B[i], T[i]}); al[B[i]].push_back({A[i],T[i]}); } int x, y; ll ans=0; for(int i=0;i<N;i++){ if(vis[i])continue; dist[i]={0, -1, 0}; dfs(i, {-1, 0}); x=i; for(auto node : curtree){ if(get<0>(dist[node])>get<0>(dist[x])){ x=node; } } for(auto node : curtree){ dist[node]={1e12, -1, 0}; } curtree.clear(); dist[x]={0, -1, 0}; dfs(x, {-1, 0}); y=x; for(auto node : curtree){ if(get<0>(dist[node])>get<0>(dist[y])){ y=node; } vis[node]=true; } curtree.clear(); ll dl=get<0>(dist[y]); ans=max(ans, dl); vector<pair<int,int>> dia; int cur=y; ll cv=dl, sm=0; while(get<1>(dist[cur]) != -1){ sm+=get<2>(dist[cur]); cv=min(cv, max(dl-sm, sm)); cur=get<1>(dist[cur]); } //~ printf("i=%d, x %d, y %d, dl is %d, cv is %d\n",i,x,y,dl, cv); guys.push_back(cv); } sort(guys.begin(),guys.end(), greater<ll>()); return max({ans, ((int)guys.size() >= 2 ? guys[0]+L+guys[1]: 0), ((int)guys.size() >= 3? guys[1]+2*L+guys[2]:0)}); }
#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...