Submission #926808

#	Time	Username	Problem	Language	Result	Execution time	Memory
926808		Art_ogo	Race (IOI11_race)	C++17	0 / 100	24 ms	74840 KiB

race

#include <bits/stdc++.h>
#include "race.h"

#define ve vector
#define ll long long
#define fi first
#define se second

using namespace std;

typedef pair<ll, ll> pll;

const int MAXN = 1e6 + 10;
ll k;

ve<pll> g[MAXN];
map<ll, ll> st[MAXN];
ll res;

void dfs(int v, int p){
    pll mx = {-1, -1};
    for(auto& to : g[v])
        if(to.fi != p){
            dfs(to.fi, v);
            if(st[v].find(k - to.se) != st[v].end())
                res = min(res, st[v][k - to.se] + 1);
            for(auto& i : st[to.fi]){
                if(st[v].find(k - (i.fi + to.se)) != st[v].end())
                    res = min(res, i.se + 1 + st[v][k - (i.fi + to.se)]);
            }
            st[v][to.se] = 1;
            for(auto i : st[to.fi])
                st[v][i.fi + to.se] = min(st[v][i.fi + to.se], i.se + 1);
        }
    if(st[v].find(k) != st[v].end())
        res = min(res, st[v][k]);
}

int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    res = 1e18;
    for(int i = 0; i < N; i++){
        g[i].clear();
       // delete(st[i]);
       st[i].clear();
    }
    for(int i = 0; i < N - 1; i++){
        g[H[i][0]].push_back({H[i][1], L[i]});
        g[H[i][1]].push_back({H[i][0], L[i]});
    }
    dfs(0, 0);
    
    return res == 1e18 ? -1 : res;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:21:9: warning: variable 'mx' set but not used [-Wunused-but-set-variable]
   21 |     pll mx = {-1, -1};
      |         ^~

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