Submission #1112852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112852		kiethm07	Race (IOI11_race)	C++11	100 / 100	410 ms	104008 KiB

race

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

#define pii pair<int,int>
#define iii pair<int,pii>
#define fi first
#define se second

#define vi vector<int>
#define all(x) x.begin(),x.end()

#define TEXT "a"

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int inf = 1e9 + 7;
const ld eps = 1e-8;
const double pi = acos(-1);
const int N = 2e5 + 5;

vector<pii> a[N];
int n;
ll k;
map<ll,int> mp[N];
int h[N], sz[N];
ll f[N];

int combine(int u,map<ll,int>& a, map<ll,int>& b){
    int res = inf;
    for (pii p : b){
        auto tmp = a.find(k - p.fi + 2 * f[u]);
        if (tmp == a.end()) continue;
        res = min(res, p.second + tmp->second - 2 * h[u]);
    }
    for (pii p : b){
        if (a.find(p.fi) != a.end()) a[p.fi] = min(a[p.fi], p.se);
        else a[p.fi] = p.se;
    }
    return res;
}

int dfs(int u,int p = -1){
    int res = inf;
    for (int i = 0; i < a[u].size(); i++){
        int v = a[u][i].fi;
        int w = a[u][i].se;
        if (v == p) continue;
        h[v] = h[u] + 1;
        f[v] = f[u] + w;
        mp[v][f[v]] = h[v];
        int tmp = dfs(v,u);
        res = min(res, tmp);
        if (mp[u].size() < mp[v].size()) swap(mp[u], mp[v]);
        res = min(res, combine(u,mp[u],mp[v]));
    }
    return res;
}

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 u = H[i][0] + 1;
        int v = H[i][1] + 1;
        int w = L[i];
        a[u].push_back(pii(v,w));
        a[v].push_back(pii(u,w));
    }
    int res = dfs(1,-1);
    if (res == inf) res = -1;
    return res;
}

Compilation message (stderr)

race.cpp: In function 'int dfs(int, int)':
race.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i = 0; i < a[u].size(); i++){
      |                     ~~^~~~~~~~~~~~~

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