Submission #1038483

#TimeUsernameProblemLanguageResultExecution timeMemory
1038483ArthuroWichDreaming (IOI13_dreaming)C++17
0 / 100
60 ms65536 KiB
#include "dreaming.h" #include<bits/stdc++.h> using namespace std; vector<pair<long long int, long long int>> adj[100005]; long long int proc[100005], no, nod, dist[100005][2]; void dfs(long long int i, long long int p, long long 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(long long int i, long long int p, long long 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(long long int i, long long 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<long long int, long long int> calc(long long int i) { long long 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 = INT64_MAX; ch(i, -1); return {nod, no}; } int travelTime(int n, int m, int l, int A[], int B[], int T[]) { vector<pair<long long int, long long int>> comp; for (long long 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 (long long int i = 0; i < n; i++) { if (proc[i]) { continue; } comp.push_back(calc(i)); } sort(comp.rbegin(), comp.rend()); deque<pair<long long int, long long int>> a; bool f = 0; for (long long int i = 0; i < comp.size(); i += 2) { a.push_front(comp[i+1]); if (i+1 < comp.size()) { a.push_back(comp[i+1]); } } for (long long int i = 1; i < a.size(); i++) { adj[a[i-1].second].push_back({a[i].second, l}); adj[a[i].second].push_back({a[i-1].second, l}); } long long int a1, b1; no = 0, nod = 0; for (long long int i = 0; i < n; i++) { dist[i][0] = 0; } dfs(0, -1, 0); a1 = no, no = 0, nod = 0; dfs(a1, -1, 0); b1 = no; dfsdist(a1, -1, 0); return dist[b1][0]; }

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:66:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (long long int i = 0; i < comp.size(); i += 2) {
      |                               ~~^~~~~~~~~~~~~
dreaming.cpp:68:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         if (i+1 < comp.size()) {
      |             ~~~~^~~~~~~~~~~~~
dreaming.cpp:72:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for (long long int i = 1; i < a.size(); i++) {
      |                               ~~^~~~~~~~~~
dreaming.cpp:65:10: warning: unused variable 'f' [-Wunused-variable]
   65 |     bool f = 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...