Submission #875552

#TimeUsernameProblemLanguageResultExecution timeMemory
875552hmm789Dreaming (IOI13_dreaming)C++14
100 / 100
45 ms16704 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; int dist[100000], prv[100000], idx; vector<pair<int, int>> adj[100000]; vector<int> v, diam, path, tmp; void dfs(int x, int p) { if(dist[x] > dist[idx]) idx = x; tmp.push_back(x); prv[x] = p; for(auto i : adj[x]) if(i.first != p) { if(dist[i.first] == -1) { dist[i.first] = dist[x]+i.second; dfs(i.first, x); } } } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { for(int i = 0; i < M; i++) { adj[A[i]].push_back({B[i], T[i]}); adj[B[i]].push_back({A[i], T[i]}); } memset(dist, -1, sizeof(dist)); for(int i = 0; i < N; i++) { if(dist[i] != -1) continue; idx = i; dist[i] = 0; dfs(i, -1); while(tmp.size()) { dist[tmp.back()] = -1; tmp.pop_back(); } dist[idx] = 0; dfs(idx, -1); tmp.clear(); int cur = (int)1e9; for(int j = idx; j != -1; j = prv[j]) path.push_back(j); for(int j : path) cur = min(cur, max(dist[j], dist[idx]-dist[j])); v.push_back(cur); diam.push_back(dist[idx]); path.clear(); } sort(v.begin(), v.end(), greater<int>()); sort(diam.begin(), diam.end(), greater<int>()); if(v.size() == 1) return diam[0]; if(v.size() == 2) return max(diam[0], v[0]+v[1]+L); return max(diam[0], max(v[0]+v[1]+L, v[1]+v[2]+2*L)); }
#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...