Submission #1267470

#TimeUsernameProblemLanguageResultExecution timeMemory
1267470WH8Dreaming (IOI13_dreaming)C++20
0 / 100
54 ms17852 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; 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]); 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>()); assert((int)guys.size() >= 2); return max(guys[0]+L+guys[1], ((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...