Submission #360203

#	Time	Username	Problem	Language	Result	Execution time	Memory
360203		ljuba	Race (IOI11_race)	C++17	100 / 100	2234 ms	119868 KiB

race

#include <bits/stdc++.h>
 
using namespace std;

typedef long long ll;
typedef long double ld;

typedef vector<int> vi;
typedef vector<ll> vll;

typedef vector<vi> vvi;
typedef vector<vll> vvll;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

typedef vector<pii> vpii;
typedef vector<pll> vpll;

typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define fi first
#define se second

template<class T> bool ckmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
template<class T> bool ckmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for(auto z : x) cerr << (f++ ? "," : ""), __print(z); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if(sizeof...(v)) cerr << ", "; _print(v...);}
 
#ifdef ljuba
#define dbg(x...) cerr << "LINE(" << __LINE__ << ") -> " << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif

const char nl = '\n';

#include "race.h"

const int mxN = 2e5 + 12;

int N;
ll k;

//prvi oznacava sumu duzina, drugi drugo
unordered_map<int, pll> dist[mxN];
unordered_map<int, int> dist2[mxN];
set<pii> adj[mxN];

int sub[mxN];

int ans = 1e9;

void dfs(int s, int p = -1) {
    sub[s] = 1;
    for(auto e : adj[s]) {
        if(e.fi == p)
            continue;
        dfs(e.fi, s);
        sub[s] += sub[e.fi];
    }
}

int centroid(int s, int p, int n) {
    for(auto e : adj[s]) {
        if(e.fi == p)
            continue;
        if(sub[e.fi] > n/2)
            return centroid(e.fi, s, n);
    }
    return s;
}

vpii tmp;

void dfs2(int s, int c, int p) {
    dbg(s, c, p, dist[c][p]);
    tmp.pb(dist[c][s]);
    for(auto e : adj[s]) {
        if(e.fi == p)
            continue;
        //dbg(s);
        dist[c][e.fi] = {dist[c][s].fi + e.se, dist[c][s].se + 1};
        int treba = k - dist[c][e.fi].fi;
        if(dist2[c].count(treba)) {
            ckmin(ans, (int)dist[c][e.fi].se + dist2[c][treba]);
        }
        dfs2(e.fi, c, s);
    }
}

void build(int s) {
    dfs(s);
    int n = sub[s];
    int c = centroid(s, -1, n);
    dbg(c);

    /*
    dist[c].reserve(1024);
    dist[c].max_load_factor(0.25);

    dist2[c].reserve(1024);
    dist2[c].max_load_factor(0.25);
    */

    dist[c][c] = {0, 0};
    dist2[c][0] = 0;

    for(auto e : adj[c]) {
        tmp.clear();
        dist[c][e.fi] = {e.se, 1};
        //tmp.pb(dist[c][e.fi]);
        //ker.pb(e.fi);
        if(dist2[c].count(k-e.se)) {
            ckmin(ans, 1 + dist2[c][k-e.se]);
        }
        dfs2(e.fi, c, c);

        for(auto z : tmp) {
            if(!dist2[c].count(z.fi)) {
                dist2[c][z.fi] = z.se;
            }
            ckmin(dist2[c][z.fi], z.se);
        }
        dbg(tmp);
    }

    if(dist2[c].count(k)) {
        ckmin(ans, dist2[c][k]);
    }

    dbg(dist[c], dist2[c]);

    dist[c].clear();
    dist2[c].clear();

    vpii temp(all(adj[c]));
    for(auto z : temp) {
        int b = z.fi;
        int w = z.se;
        adj[c].erase({b, w});
        adj[b].erase({c, w});
        build(b);
    }
}

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 a = H[i][0], b = H[i][1];
        int w = L[i];
        adj[a].insert({b, w});
        adj[b].insert({a, w});
    }

    build(0);
    dbg(dist[2][0]);

    return (ans == 1e9 ? -1 : ans);
}

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