Submission #682910

#	Time	Username	Problem	Language	Result	Execution time	Memory
682910		whqkrtk04	Race (IOI11_race)	C++17	100 / 100	387 ms	97488 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000007;
const ll LLINF = (ll)1e18+1;
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rnd(x, y) uniform_int_distribution<int>(x, y)(rng)

ll mod(ll a, ll b) { return ((a%b) + b) % b; }
ll ext_gcd(ll a, ll b, ll &x, ll &y) {
    ll g = a; x = 1, y = 0;
    if(b) g = ext_gcd(b, a % b, y, x), y -= a / b * x;
    return g;
}
ll inv(ll a, ll m) {
    ll x, y; ll g = ext_gcd(a, m, x, y);
    if(g > 1) return -1;
    return mod(x, m);
}

int dfs(int x, ll d, int l, vector<vector<pii>> &E,
        vector<int> &len, vector<int> &siz, vector<ll> &dep) {
    siz[x] = 1; len[x] = l; dep[x] = d;
    for(auto &i : E[x]) {
        E[i.fi].erase(find(E[i.fi].begin(), E[i.fi].end(), pii(x, i.se)));
        siz[x] += dfs(i.fi, d+i.se, l+1, E, len, siz, dep);
        if(siz[i.fi] > siz[E[x][0].fi]) swap(i, E[x][0]);
    }
    return siz[x];
}

int val(set<pll> *S, ll k, const pll &x, const pll &i) {
    ll tmp = k+2*x.fi-i.fi;
    auto iter = S->lower_bound({tmp, 0LL});
    if(iter == S->end() || iter->fi != tmp) return INF;
    return iter->se+i.se-2*x.se;
}

int solve(int x, ll k, vector<vector<pii>> &E,
        vector<int> &len, vector<int> &siz, vector<ll> &dep, vector<set<pll>*> &S) {
    if(E[x].empty()) {
        S[x] = new set<pll>;
        S[x]->insert({dep[x], len[x]});
        return INF;
    }

    int ans = INF;
    for(auto &i : E[x]) ans = min(ans, solve(i.fi, k, E, len, siz, dep, S));
    S[x] = S[E[x][0].fi];
    pll tmp = {dep[x], len[x]};
    for(int i = 1; i < E[x].size(); i++) {
        for(auto &j : *S[E[x][i].fi]) ans = min(ans, val(S[x], k, tmp, j));
        for(auto &j : *S[E[x][i].fi]) S[x]->insert(j);
    }
    ans = min(ans, val(S[x], k, tmp, tmp));
    S[x]->insert(tmp);
    return ans;
}

int best_path(int N, int K, int H[][2], int L[]) {
    vector<vector<pii>> E(N);
    for(int i = 0; i+1 < N; i++) {
        E[H[i][0]].push_back({H[i][1], L[i]});
        E[H[i][1]].push_back({H[i][0], L[i]});
    }
    vector<ll> dep(N);
    vector<int> len(N), siz(N);
    dfs(0, 0LL, 0, E, len, siz, dep);
    vector<set<pll>*> S(N, nullptr);
    int ans = solve(0, K, E, len, siz, dep, S);
    if(ans == INF) return -1;
    else return ans;
}

Compilation message (stderr)

race.cpp: In function 'int solve(int, ll, std::vector<std::vector<std::pair<int, int> > >&, std::vector<int>&, std::vector<int>&, std::vector<long long int>&, std::vector<std::set<std::pair<long long int, long long int> >*>&)':
race.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i = 1; i < E[x].size(); i++) {
      |                    ~~^~~~~~~~~~~~~

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