Submission #32808

#	Time	Username	Problem	Language	Result	Execution time	Memory
32808		Mamnoon_Siam	Race (IOI11_race)	C++14	100 / 100	2176 ms	162272 KiB

race

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

#define wait() system("pause")
#define clock_starts() clock_t begin = clock()
#define clock_ends() clock_t end = clock()
#define print_running_time() double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC; \
printf("Elapsed Time : %.10f second(s)\n", elapsed_secs)
#define read(s) freopen(s, "r", stdin)
#define write(s) freopen(s, "w", stdout)
#define debug(s) cout<< #s <<" = "<< s <<endl
#define int long long
#define inf 1000000000000000000LL

const int maxn = 200010;

bool onCtree[maxn]; int n, k;
vector<pair<int, int>> v[maxn];
vector<int> ctree[maxn], subtree[maxn];
int level[maxn], T[19][maxn], sub[maxn], D[maxn], parent[maxn];
map<int, int> mp; int ret = inf;
vector<int> eulerTour; int lg[maxn*2], where[maxn], table[19][maxn*2];

void preCalc(int p, int node, int l, int d) {
    level[node] = l; eulerTour.push_back(node);
    D[node] = d, T[0][node] = parent[node] = p;
    for(auto b : v[node]) {
        if(b.first != p) {
            preCalc(node, b.first, l+1, d+b.second);
            eulerTour.push_back(node);
        }
    }
}

int MIN(int a, int b) { // I can easily believe that where O(1)
                        // lca needed there is a level[] array :/
    return ( level[a] < level[b] ? a : b ) ;
}

void makeTable() {
    int N = eulerTour.size()-1;
    for(int i=0; i<maxn; i++) where[i] = inf;
    for(int i=0; i<=N; i++) where[eulerTour[i]] = min(where[eulerTour[i]], i);
    for(int i=0; i<=N; i++) table[0][i] = eulerTour[i];
    lg[1] = 0; for(int i=2; i<=N; i++) lg[i] = lg[i >> 1] + 1;
    for(int p=1; p<20; p++) {
        for(int i=0; i+(1<<p)-1<=N; i++) {
            table[p][i] = MIN(table[p-1][i], table[p-1][i+(1<<(p-1))]);
        }
    }
}

int getMin(int l, int r) {
    int k = lg[r-l+1];
    return MIN(table[k][l], table[k][r-(1<<k)+1]);
}

int __lca(int a, int b) {
    if(where[a] > where[b]) swap(a, b);
    return getMin(where[a], where[b]);
}

int cost(int x, int y) {
    return D[x] + D[y] - 2 * D[__lca(x, y)];
}

int dist(int x, int y) {
    return level[x] + level[y] - 2 * level[__lca(x, y)];
}

void dfs(int p, int node) {
    sub[node] = 1;
    for(auto b : v[node]) {
        if(!onCtree[b.first] and p != b.first) {
            dfs(node, b.first);
            sub[node] += sub[b.first];
        }
    }
}

int decompose(int p, int node, int sz) {
    for(auto b : v[node]) {
        if(!onCtree[b.first] and b.first != p and sub[b.first] > sz/2) {
            return decompose(node, b.first, sz);
        }
    }
    onCtree[node] = true;
    for(auto b : v[node]) {
        if(!onCtree[b.first]) {
            dfs(node, b.first);
            ctree[node].push_back(decompose(node, b.first, sub[b.first]));
        }
    } return node;
}

void add(int node) {
    subtree[node].push_back(node);
    for(auto b : ctree[node]) {
        add(b);
        for(auto x : subtree[b]) {
            subtree[node].push_back(x);
        }
    }
}

void solve() {
    preCalc(-1,1,0,0);
    //process();
    makeTable();
    dfs(-1,1);
    int root = decompose(-1,1, sub[1]);
    add(root);
    for(int i=1; i<=n; i++) ctree[i].reserve(ctree[i].size());
    for(int i=1; i<=n; i++) subtree[i].reserve(subtree[i].size());
    for(int i=1; i<=n; i++) {
        for(auto b : ctree[i]) {
            for(auto node : subtree[b]) {
                //int d = cost(i, node);
                int lca = __lca(i, node);
                int d = D[i] + D[node] - 2 * D[lca];
                if(mp.find(k-d) != mp.end()) {
                    //ret = min(ret, dist(i, node)+mp[k-d]);
                    ret = min(ret, level[i] + level[node] - 2 * level[lca] + mp[k-d]);
                }
            }
            for(auto node : subtree[b]) {
                //int d = cost(i, node);
                int lca = __lca(i, node);
                int d = D[i] + D[node] - 2 * D[lca];
                if(mp.find(d) != mp.end()) {
                    mp[d] = min(mp[d], level[i] + level[node] - 2 * level[lca]);
                } else mp[d] = level[i] + level[node] - 2 * level[lca];
            }
        }
        if(mp.find(k) != mp.end()) {
            ret = min( ret , mp[k] );
        }
        mp.clear();
    }
}

int32_t best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[]) {
    n = N, k = K;
    for(int i=0; i<n-1; i++) {
        int x = H[i][0]+1, y = H[i][1]+1, w = L[i];
        v[x].push_back({y, w});
        v[y].push_back({x, w});
    }
    if(k==0) return 0;
    solve();
    if(ret == inf) return -1;
    return (int32_t)ret;
}
/*
int32_t main () {
    cin>>n>>k;
    for(int i=1; i<n; i++) {
        int x, y, w; scanf("%lld%lld%lld", &x, &y, &w);
        x++, y++;
        v[x].push_back({y, w});
        v[y].push_back({x, w});
    }
    if(k==0) {
        puts("0");
        return 0;
    }
    solve();
    if(ret == inf) {
        puts("-1");
    } else {
        printf("%lld\n", ret);
    }
    //wait();
    return 0;
}
*/

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