Submission #1040254

#TimeUsernameProblemLanguageResultExecution timeMemory
1040254DeathIsAweDreaming (IOI13_dreaming)C++14
47 / 100
43 ms14256 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; vector<vector<pair<int,int>>> graph; vector<pair<int,int>> dum; vector<int> radi, parent, stac, sum; vector<bool> visited; void recur(int a) { for (pair<int,int> i: graph[a]) { if (i.first != parent[a]) { recur(i.first); sum[a] = max(sum[a], sum[i.first] + i.second); } } } int travelTime(int n, int m, int l, int a[], int b[], int t[]) { int node, radius, prevsum, next, radiusprev, temp, temp2, diameter = 0, maxdi; bool button; for (int i=0;i<n;i++) { visited.push_back(false); sum.push_back(0); graph.push_back(dum); parent.push_back(0); } for (int i=0;i<m;i++) { graph[a[i]].push_back(make_pair(b[i], t[i])); graph[b[i]].push_back(make_pair(a[i], t[i])); } for (int i=0;i<n;i++) { if (visited[i]) { continue; } if (graph[i].size() == 0) { visited[i] = true; radi.push_back(0); continue; } if (graph[i].size() != 1) { continue; } stac = {i}; parent[i] = -1; while (stac.size() > 0) { node = stac.back(); stac.pop_back(); visited[node] = true; for (pair<int,int> j: graph[node]) { if (j.first != parent[node]) { parent[j.first] = node; stac.push_back(j.first); } } } recur(i); radius = sum[i]; prevsum = 0; radiusprev = INT_MAX; node = i; diameter = sum[i]; while (radiusprev > radius) { for (pair<int,int> j: graph[node]) { if (j.first == parent[node]) { continue; } if (sum[j.first] + j.second == sum[node]) { next = j.first; temp2 = j.second; } } temp = 0; button = false; for (pair<int,int> j: graph[next]) { if (j.first == parent[next]) { continue; } if (!button && sum[j.first] + j.second == sum[next]) { button = true; continue; } temp = max(temp, sum[j.first] + j.second); } diameter = max(diameter, temp + sum[next]); prevsum = max(prevsum + temp2, temp); radiusprev = radius; radius = max(prevsum, sum[next]); node = next; //cout << radiusprev << ' ' << radius << ' ' << prevsum << '\n'; } //cout << radiusprev << '\n' << '\n'; radi.push_back(radiusprev); maxdi = max(maxdi, diameter); } //for (int i: radi) { // cout << i << ' '; //} //cout << '\n'; sort(radi.begin(), radi.end(), greater<int>()); if (radi.size() == 1) { return maxdi; } else if (radi.size() == 2) { return max(radi[0] + radi[1] + l, maxdi); } return max(max(radi[0] + radi[1], radi[1] + radi[2] + l) + l, maxdi); }

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:21:77: warning: 'maxdi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   21 |     int node, radius, prevsum, next, radiusprev, temp, temp2, diameter = 0, maxdi;
      |                                                                             ^~~~~
dreaming.cpp:87:35: warning: 'temp2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |             prevsum = max(prevsum + temp2, temp);
      |                           ~~~~~~~~^~~~~~~
dreaming.cpp:76:45: warning: 'next' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |             for (pair<int,int> j: graph[next]) {
      |                                             ^
#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...