제출 #1241560

#제출 시각아이디문제언어결과실행 시간메모리
1241560papauloDreaming (IOI13_dreaming)C++20
0 / 100
30 ms13376 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; #define MAXN 100100 int dist[MAXN]; int visited[MAXN]; int far; int pai[MAXN]; vector<pair<int, int>> adj[MAXN]; void dfs(int v, int p) { visited[v]=1; pai[v]=p; if(dist[v]>dist[far]) far=v; for(auto e : adj[v]) { if(e.first==p) continue; dist[e.first]=dist[v]+e.second; dfs(e.first, v); } } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { memset(visited, 0, sizeof(visited)); 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]}); } vector<int> trees; for(int i=0;i<N;i++) { if(visited[i]) continue; dist[i]=0; far=i; dfs(i, -1); dist[far]=0; dfs(far, -1); int v=far; int bst=1e9; while(v!=-1) { bst=min(bst, max(dist[v], dist[far]-dist[v])); v=pai[v]; } trees.push_back(bst); } sort(trees.rbegin(), trees.rend()); deque<int> dq; for(int i=0;i<trees.size();i++) { int t=trees[i]; if(i%2==0) dq.push_back(t); else dq.push_front(t); } int ans=0; int curFar=0; for(auto t : dq) { ans=max(ans, t+curFar); curFar=max(curFar, t)+L; } return ans; }
#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...