Submission #659860

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
659860	2022-11-19 14:23:46	Trisanu_Das	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std; 
int K, ans = INT_MAX; vector<pair<int, int>> adj[200005]; set<pair<int, int>> S[200005];
 
void dfs(int u, int p, int dis, int dep){
    S[u].insert({dis, dep});
    for (auto v : adj[u]) if (v.first != p){
        dfs(v.first, u, dis + v.second, dep + 1);
        if (S[u].size() < S[v.first].size()) swap(S[u], S[v.first]);
        for (auto d : S[v.first]){
            int other = K + 2 * dis - d.first; auto x = S[u].lower_bound({other, -1});
            if (x != S[u].end() and (*x).first == other) ans = min(ans, d.second + (*x).second - 2 * dep);
        }for (auto d : S[v.first]) S[u].insert(d);
    }
}
int best_path(int n, int k, int h[][2], int l[]){
    for (int i = 0; i < n - 1; i++){
        adj[h[i][0]].push_back({h[i][1], l[i]});
        adj[h[i][1]].push_back({h[i][0], l[i]});
    }K = k; dfs(0, 0, 0, 0); return (ans == INT_MAX) ? -1 : ans;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:20:64: error: expected '}' at end of input
   20 |     }K = k; dfs(0, 0, 0, 0); return (ans == INT_MAX) ? -1 : ans;
      |                                                                ^
race.cpp:16:49: note: to match this '{'
   16 | int best_path(int n, int k, int h[][2], int l[]){
      |                                                 ^