Submission #694541

#	Time	Username	Problem	Language	Result	Execution time	Memory
694541		ac2hu	Race (IOI11_race)	C++14	21 / 100	174 ms	17216 KiB

race

#include <bits/stdc++.h>
using namespace std;
#include "race.h"
#define int long long 
const int MX = 2e5 + 10;
int n, k, ans = 1e9, timer = 0, tin[MX], tout[MX], rev[MX], d[MX], ed[MX], siz[MX], bigc[MX];
vector<pair<int,int>> adj[MX];
map<int, int> mnedge;
void dfs2(int v,int p, bool keep){// keep
    for(auto [e, w] : adj[v]){
        if(p != e && bigc[v] != e)dfs2(e, v, false);
    }
    if(bigc[v] != -1)dfs2(bigc[v], v, true);
    mnedge[d[v]] = ed[v];
    if(mnedge.find(d[v] + k) != mnedge.end())
        ans = min(ans, mnedge[d[v] + k] - ed[v]);
    for(auto [e, w] : adj[v]){
        if(e == p || e == bigc[v])continue;
        for(int st = tin[e];st<=tout[e];st++){
            int node = rev[st];
            // d[node] + d[x] - 2*d[v] = k => d[x] = k + 2*d[v] - d[node] 
            int c = k + 2*d[v] - d[node];
            if(mnedge.find(c) != mnedge.end())ans = min(ans, mnedge[c] + ed[node] - 2*ed[v]);
        }
        for(int st = tin[e];st<=tout[e];st++){
            if(mnedge[d[rev[st]]] == 0)
                mnedge[d[rev[st]]] = ed[rev[st]];
            else 
                mnedge[d[rev[st]]] = min(mnedge[d[rev[st]]], ed[rev[st]]);
        }
    }
    if(!keep){
        mnedge.clear();
    }
}
void dfs1(int v,int p){
    int mx = -1;
    rev[timer] = v;
    tin[v] = timer++;
    bigc[v] = -1;
    siz[v] = 1;
    for(auto [e, w] : adj[v]){
        if(e == p)continue;
        d[e] = d[v] + w;
        ed[e] = ed[v] + 1;
        dfs1(e, v);
        if(siz[e] > mx){
            bigc[v] = e;
            mx = siz[e];
        }
        siz[v] += siz[e];
    }
    tout[v] = timer;
}
#undef int
int best_path(int N, int K, int H[][2], int L[]){
    n = N, k = K;
    for(int i = 0;i + 1<n;i++){
        int a = H[i][0], b = H[i][1], c = L[i];
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    dfs1(0, -1);
    dfs2(0, -1, true);
    if(ans > 1e8)
        return -1;
    return ans;
}
// signed main() {
//     iostream::sync_with_stdio(0);cin.tie(0);
// }

Compilation message (stderr)

race.cpp: In function 'void dfs2(long long int, long long 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[v]){
      |              ^
race.cpp:17:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |     for(auto [e, w] : adj[v]){
      |              ^
race.cpp: In function 'void dfs1(long long int, long long int)':
race.cpp:42:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     for(auto [e, w] : adj[v]){
      |              ^

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