Submission #739722

#	Time	Username	Problem	Language	Result	Execution time	Memory
739722		swagchicken	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef vector<int> vi;
typedef vector< vector <int> > vvi;
typedef pair<int, int> pii;
typedef pair < pair < int, int >, int > piii;
typedef pair < pair <int, int > , pair <int, int> > piiii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
 
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define RFOR(i,a,b) for(int i = a-1; i >= b; i --)
#define all(a) a.begin(), a.end()
#define endl '\n';
#define sz(x) (int)(x).size()
 
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
 

vector<vector<pair<int, ll>>> adj;
vector<ll> dep, dist;

vector<map<ll, ll>> paths;
ll N,K;
ll ans = 1e9;

void dfs(int u, int p, ll d, ll ds) {
    dep[u] = d;
    dist[u] = ds;
    for(auto x : adj[u]) {
        ll w = x.ss;
        int v = x.ff;
        if(v != p) {
            dfs(v, u, d + 1, ds + w);
        }
    }
}

void dfs2(int u, int p, ll d, ll ds) {
    
    ll tar = k + 2 * ds;
    paths[u][ds] = d;

    for(auto x : adj[u]) {
        ll w = x.ss;
        int v = x.ff;
        if(v != p) {
            dfs2(v, u, d + 1, ds + w);
            
            if(paths[v].size() > paths[u].size()) {
                swap(paths[u], paths[v]);
            }

            for(auto y : paths[v]) {
                if(paths[u].count(tar - y.ff)) {
                    ans = min(ans, paths[u][tar-y.ff] + y.ss - 2 * d);
                }
            }
            for(auto y : paths[v]) {
                if(paths[u].count(y.ff)) {
                    paths[u][y.ff] = min(paths[u][y.ff], y.ss);
                } else {
                    paths[u][y.ff] = y.ss;
                }
            }

        }

    }

    if(paths[u].count(k + ds)) {
        ans = min(ans, paths[u][k+ds] - d);
    }
}   

int best_path(int n, int k, int edges[][2], int weights[]) {
    adj.resize(n);
    dist.resize(n);
    dep.resize(n);
    paths.resize(n);

    
	FOR(i,0,n-1) {
        ll u = edges[i][0];
        ll v = edges[i][1];
        ll w = weights[i];
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }

    dfs(0,0,0,0);
    dfs2(0,0,0,0);

    if(ans == 1e9) ans = -1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs2(int, int, ll, ll)':
race.cpp:50:14: error: 'k' was not declared in this scope
   50 |     ll tar = k + 2 * ds;
      |              ^