Submission #1040251

#TimeUsernameProblemLanguageResultExecution timeMemory
1040251DeathIsAweDreaming (IOI13_dreaming)C++14
0 / 100
32 ms27388 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; 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); //for (int i=0;i<n;i++) { // cout << sum [i] << ' '; //} //cout << '\n'; radius = sum[i]; prevsum = 0; radiusprev = INT_MAX; node = 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); } 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); } //for (int i: radi) { // cout << i << ' '; //} //cout << '\n'; sort(radi.begin(), radi.end(), greater<int>()); if (radi.size() == 1) { return radi[0]; } else if (radi.size() == 2) { return radi[0] + radi[1] + l; } return max(radi[0] + radi[1], radi[1] + radi[2] + l) + 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...