Submission #550963

#	Time	Username	Problem	Language	Result	Execution time	Memory
550963		ac2hu	Race (IOI11_race)	C++14	100 / 100	494 ms	62708 KiB

race

#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];
                if(hold[d[id]] == 0)
                    hold[d[id]] = edges[id];
                else
                    hold[d[id]] = min(hold[d[id]], edges[id]);
            }
        }
    }
    if(!keep){
        hold.clear();
    }
}
void dfs1(int i,int p){
    int tt = -1;
    big[i] = -1;
    siz[i] = 1;
    st[++timer] = i;
    tin[i] = timer;
    big[i] = -1;
    for(auto [e, w] : adj[i]){
        if(e == p)continue;
        d[e] = d[i] + w;
        edges[e] = edges[i] + 1;
        dfs1(e, i);
        siz[i] += siz[e];
        if(siz[e] > tt){
            big[i] = e;
            tt = siz[e];
        }
    }
    tout[i] = timer;
}
int best_path(int N, int K, int H[][2], int L[]){
    n = N;
    k = K;
    for(int i = 0;i<n - 1;i++){
        int a = H[i][0],b = H[i][1], w = L[i];
        adj[a].push_back({b,w});
        adj[b].push_back({a,w});
    }
    d[0] = 0;
    dfs1(0, -1);
    dfs2(0,-1,true);
    if(ans > N)
        ans = -1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs2(int, int, bool)':
race.cpp:10:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   10 |     for(auto [e, w] : adj[i]){
      |              ^
race.cpp:20:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |     for(auto [e, w] : adj[i]){
      |              ^
race.cpp: In function 'void dfs1(int, int)':
race.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |     for(auto [e, w] : adj[i]){
      |              ^

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57