Submission #941330

#	Time	Username	Problem	Language	Result	Execution time	Memory
941330		Mike_Vu	Race (IOI11_race)	C++14	0 / 100	3 ms	12892 KiB

race

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second

//const ll mod = 1e9+7;

bool maximize(ll &x, ll y ){
    if (x < y) {x = y; return true;};
    return false;
}
bool minimize(int &x, int y){
    if (x > y) {x = y; return true;}
    return false;
}
//void add(ll &x, ll y ){
//    x += y;
//    if (x >= mod) x -= mod;
//}
//void sub(ll &x, ll y) {
//    x -= y;
//    if (x < 0) x += mod;
//}

const int maxn = 2e5+5;
const int maxx = 1e9+7;

int n, k;
vector<pii> a[maxn];

bitset<maxn> del;
int child[maxn];
int sz, root;

int ans = maxx;

void couchild(int u, int p) {
    child[u] = 1;
    for (int i = 0; i <(int)a[u].size(); i++) {
        int v = a[u][i].fi;
        if (v == p || del[v]) continue;
        couchild(v, u);
        child[u] += child[v];
    }
}
int centroid(int u, int p) {
    for (int i = 0 ;i < (int)a[u].size(); i++) {
        int v = a[u][i].fi;
        if (v == p || del[v]) continue;
        if (child[v] >= (sz >> 1)) return centroid(v, u);
    }
    return u;
}

int h[maxn];
int dis[maxn];
int tk[1000007];
vector<pii> temp;

void dfs(int u, int p) {
    temp.push_back({dis[u], h[u]});
    if (tk[k-dis[u]] < maxx) {
        minimize(ans, h[u] + tk[k-dis[u]]);
    }
    for (int i = 0; i < (int)a[u].size(); i++) {
        int v = a[u][i].fi;
        if (v == p || del[v]) continue;
        int w = a[u][i].se;
        if (dis[u] + w > k) continue;
        dis[v] = dis[u] + w;
        h[v] = h[u] + 1;
        dfs(v, u);
    }
}

void dfsr(int u, int p) {
    tk[dis[u]] = maxx;
    for (int i = 0; i < (int)a[u].size(); i++) {
        int v = a[u][i].fi;
        if (v == p || del[v]) continue;
        int w = a[u][i].se;
        if (dis[u] + w > k) continue;
        dfsr(v, u);
    }
}

void solve(int u) {
    couchild(u, 0);
    sz = child[u];
    //get centroid
    root = centroid(u, 0);
    //dfs solve
    h[root] = dis[root] = 0;
    for (int i = 0; i < (int)a[root].size(); i++) {
        int v = a[u][i].first, w = a[u][i].se;
        if (del[v]) continue;
        if (w > k) continue;
        dis[v] = dis[u] + w;
        h[v] = h[u]+1;
        dfs(v, u);
        for (int i = 0; i < (int)temp.size(); i++) {
            minimize(tk[temp[i].fi], temp[i].se);
        }
        temp.clear();
    }
    //dfs erase
    dfsr(root, 0);
    del[root] = true;
    //solve sub
    for (int i = 0; i < (int)a[root].size(); i++) {
        int v = a[u][i].first;
        if (del[v]) continue;
        solve(v);
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N;
    k = K;
    for (int i = 1; i <= n; i++) {
        int u = H[i][0], v = H[i][1];
        int w = L[i];
        a[u].pb({v, w});
        a[v].pb({u, w});
    }
    for (int i = 1; i <= k; i++) {
        tk[i] = maxx;
    }
    solve(1);
    return ans;
}

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