# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
59600 | spencercompton | Dreaming (IOI13_dreaming) | C++17 | 113 ms | 26488 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[100000];
vector<int> adjw[100000];
int sub[100000];
bool v[100000];
int dfs1(int now, int from){
v[now] = true;
sub[now] = 0;
for(int i = 0; i<adj[now].size(); i++){
int to = adj[now][i];
if(to==from){
continue;
}
sub[now] = max(sub[now],adjw[now][i] + dfs1(to, now));
}
return sub[now];
}
int dfs2(int now, int from, int above){
int ret = 1000000007;
vector<pair<int, int> > li;
//deep, loc
for(int i = 0; i<adj[now].size(); i++){
int to = adj[now][i];
if(to==from){
continue;
}
li.push_back(make_pair(sub[to]+adjw[now][i],to));
}
if(li.size()==0){
return above;
}
int maxi = 0;
for(int i = 1; i<li.size(); i++){
if(li[i].first > li[maxi].first){
maxi = i;
}
}
ret = min(ret, max(above,li[maxi].first));
for(int i = 0; i<li.size(); i++){
if(i==maxi){
continue;
}
above = max(above,li[i].first);
}
above += adjw[now][maxi];
ret = min(ret, dfs2(adj[now][maxi],now,above));
return ret;
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
for(int i = 0; i<m; i++){
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
adjw[a[i]].push_back(t[i]);
adjw[b[i]].push_back(t[i]);
}
for(int i = 0; i<n; i++){
v[i] = false;
}
vector<int> all;
for(int i = 0; i<n; i++){
if(adj[i].size()==0){
v[i] = true;
all.push_back(0);
}
if(v[i] || adj[i].size()!=1){
continue;
}
dfs1(i,-1);
all.push_back(dfs2(i,-1,0));
}
for(int i = 0; i<n; i++){
assert(v[i]);
}
priority_queue<int> pq;
for(int i = 0; i<all.size(); i++){
pq.push(-all[i]);
while(pq.size()>2){
pq.pop();
}
}
if(pq.size()==1){
return -pq.top();
}
int ans = l + -pq.top();
pq.pop();
ans -= pq.top();
return ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |