(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

제출 #1084203

#제출 시각아이디문제언어결과실행 시간메모리
1084203pera꿈 (IOI13_dreaming)C++17
0 / 100
48 ms21852 KiB
#include<bits/stdc++.h> #include "dreaming.h" using namespace std; int travelTime(int N , int M , int L , int A[] , int B[] , int T[]){ vector<vector<int>> g(N + 1) , w(N + 1); auto add_edge = [&](int u , int v , int weight){ g[u].emplace_back(v); w[u].emplace_back(weight); }; for(int i = 0;i < M;i ++){ ++A[i],++B[i]; add_edge(A[i] , B[i] , T[i]); add_edge(B[i] , A[i] , T[i]); } vector<int> visited(N + 1) , d(N + 1) , mx(N + 1) , non_sub(N + 1) , max_depths; function<void(int , int)> dfs = [&](int u , int p){ for(int x = 0;x < (int)g[u].size();x ++){ if(g[u][x] != p){ d[g[u][x]] = d[u] + w[u][x]; dfs(g[u][x] , u); mx[u] = max(mx[u] , mx[g[u][x]] + w[u][x]); } } }; function<int(int)> DFS = [&](int u){ visited[u] = 1; int mn = max(mx[u] , non_sub[u]); multiset<int> X; for(int x = 0;x < (int)g[u].size();x ++){ if(visited[g[u][x]] == 0){ X.insert(mx[g[u][x]] + w[u][x]); } } for(int x = 0;x < (int)g[u].size();x ++){ if(visited[g[u][x]] == 0){ X.erase(X.find(mx[g[u][x]] + w[u][x])); non_sub[g[u][x]] = max(non_sub[u] , (X.empty() ? 0 : *--X.end())) + w[u][x]; mn = min(mn , DFS(g[u][x])); X.insert(mx[g[u][x]] + w[u][x]); } } return mn; }; for(int i = 1;i <= N;i ++){ if(visited[i] == 0){ dfs(i , -1); max_depths.emplace_back(DFS(i)); } } int sz = max_depths.size(); sort(max_depths.begin() , max_depths.end()); if(sz == 2){ return max_depths[0] + max_depths[1] + L; } return max(max_depths[sz - 1] + max_depths[sz - 2] + L , max_depths[sz - 2] + max_depths[sz - 3] + 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...