Submission #1038498

#TimeUsernameProblemLanguageResultExecution timeMemory
1038498ArthuroWichDreaming (IOI13_dreaming)C++17
100 / 100
64 ms15956 KiB
#include "dreaming.h" #include<bits/stdc++.h> using namespace std; vector<pair<int, int>> adj[100005]; int proc[100005], no, nod, dist[100005][2]; void dfs(int i, int p, int d) { if (d > nod) { no = i, nod = d; } proc[i] = 1; for (auto [j, w] : adj[i]) { if (j == p) { continue; } dfs(j, i, d+w); } } void dfsdist(int i, int p, int id) { for (auto [j, w] : adj[i]) { if (j == p) { continue; } dist[j][id] = dist[i][id]+w; dfsdist(j, i, id); } } void ch(int i, int p) { if (max(dist[i][0], dist[i][1]) < nod) { no = i, nod = max(dist[i][0], dist[i][1]); } for (auto [j, _] : adj[i]) { if (j == p) { continue; } ch(j, i); } } pair<int, int> calc(int i) { int a, b; no = i, nod = 0; dfs(i, -1, 0); a = no, no = i, nod = 0; dfs(a, -1, 0); b = no; dfsdist(a, -1, 0); dfsdist(b, -1, 1); no = i, nod = INT_MAX; ch(i, -1); return {nod, no}; } int travelTime(int n, int m, int l, int A[], int B[], int T[]) { vector<pair<int, int>> comp; 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]}); } for (int i = 0; i < n; i++) { if (proc[i]) { continue; } comp.push_back(calc(i)); } sort(comp.rbegin(), comp.rend()); for (int i = 1; i < comp.size(); i++) { adj[comp[0].second].push_back({comp[i].second, l}); adj[comp[i].second].push_back({comp[0].second, l}); } int a, b; no = 0, nod = 0; for (int i = 0; i < n; i++) { dist[i][0] = 0; } dfs(0, -1, 0); a = no, no = 0, nod = 0; dfs(a, -1, 0); b = no; dfsdist(a, -1, 0); return dist[b][0]; }

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int i = 1; i < comp.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
#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...