Submission #1260361

#TimeUsernameProblemLanguageResultExecution timeMemory
1260361repmann꿈 (IOI13_dreaming)C++20
59 / 100
1096 ms41068 KiB
#include <bits/stdc++.h> #include "dreaming.h" using namespace std; int N, M, L; int DP[2][1000001]; vector <pair <int, int>> VG[1000001]; inline pair <int, int> DFS(int node, int parent = 0) { pair <int, int> ret = {DP[0][node], node}; for(pair <int, int> p : VG[node]) { if(p.second == parent) continue; DP[0][p.second] = DP[0][node] + p.first; ret = max(DFS(p.second, node), ret); } return ret; } inline int MDFS(int node, int parent = 0) { int ret = max(DP[0][node], DP[1][node]); for(pair <int, int> p : VG[node]) if(p.second != parent) ret = min(MDFS(p.second, node), ret); return ret; } inline pair <int, int> Diameter(int node) { int u = DFS(node).second; DP[0][u] = 0; int v = DFS(u).second; swap(DP[0], DP[1]); int diameter = DFS(v).first; int minimum = MDFS(v); return {diameter, minimum}; } int travelTime(int n, int m, int l, int u[], int v[], int w[]) { N = n; M = m; L = l; for(int i = 0; i < M; i++) { VG[u[i] + 1].push_back({w[i], v[i] + 1}); VG[v[i] + 1].push_back({w[i], u[i] + 1}); } int diameter = 0, maximum[3]; maximum[0] = maximum[1] = maximum[2] = 0; for(int i = 1; i <= N; i++) { if(DP[0][i] || DP[1][i] || !VG[i].size()) continue; // cout << i << ":\n"; pair <int, int> temp = Diameter(i); if(!temp.first) continue; // cout << temp.first << ' ' << temp.second << '\n'; diameter = max(temp.first, diameter); for(int j = 0; j < 3; j++) { if(temp.second <= maximum[j]) continue; for(int k = 2; k > j; k--) maximum[k] = maximum[k - 1]; maximum[j] = temp.second; break; } } // cout << "maximum:\n"; // for(int j = 0; j < 3; j++) cout << maximum[j] << " \n"[j == 2]; if(M == (N - 1)) return diameter; if(M == (N - 2)) return max(diameter, maximum[0] + maximum[1] + L); return max({diameter, maximum[0] + maximum[1] + L, maximum[1] + maximum[2] + L + L}); } //int main() //{ // int n, m, l, u[100], v[100], w[100]; // cin >> n >> m >> l; // for(int i = 0; i < m; i++) cin >> u[i] >> v[i] >> w[i]; // cout << travelTime(n, m, l, u, v, w) << '\n'; // // return 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...