# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
550960 | ac2hu | Race (IOI11_race) | C++14 | 1074 ms | 65956 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<bits/stdc++.h>
using namespace std;
#include "race.h"
// Do everything in global distance because it simplifies work
const int MX = 2e5 + 10;
int ans = 1e9, n, k, timer = 0, d[MX], tin[MX], tout[MX], st[MX], big[MX], siz[MX], edges[MX];
vector<pair<int,int>> adj[MX];
map<int,int> hold;
void dfs2(int i,int p,bool keep){
for(auto [e, w] : adj[i]){
if(e != p && e != big[i]) dfs2(e, i,false);
}
if(big[i] != -1)
dfs2(big[i], i, true);
hold[d[i]] = edges[i];
int total = k + 2*d[i];
if(hold.find(total - d[i]) != hold.end()){
ans = min(ans, hold[total - d[i]] - edges[i]);
}
for(auto [e, w] : adj[i]){
if(e != p && e != big[i]){
for(int tim = tin[e];tim<=tout[e];tim++){
int id = st[tim];
if(hold.find(total - d[id]) != hold.end()){
ans = min(ans, hold[total - d[id]] + edges[id] - 2*edges[i]);
}
}
for(int tim = tin[e];tim<=tout[e];tim++){
int id = st[tim];
hold[d[id]] = min(hold[d[id]], edges[id]);
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... |