Submission #1283122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283122		diep38	Race (IOI11_race)	C++17	100 / 100	1002 ms	61604 KiB

race

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

#define ed "\n"
#define fi first
#define se second
#define irs insert
#define pb push_back
#define pi pair<int,int>
#define MASK(i) (1LL << (i))
#define BIT(x, i) ((x>>i)&1)
#define ON(x, i) ((x)  MASK(i))
#define OFF(x, i) ((x) & ~MASK(i))
#define ALL(v) v.begin() , v.end()
#define pii pair<int,pair<int,int>>
#define fl(i,a,b) for(int i=a;i>=b;--i)
#define fis(i,a,b) for(int i=a;i<=b;++i)
const int mod=1e9+7;
const int Mdem=998244353;
const int LOG=19;
const int base=31;
const int maxn=2e5+5;
const int bl = 320;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define gay(a) freopen(a".inp","r",stdin),freopen(a".out","w",stdout)
template <class T>
bool minimize(T &a, const T &b) {
    if(a > b) {a = b; return 1;}
    return 0;
}

template <class T>
bool maximize(T &a, const T &b) {
    if(a < b) {a = b; return 1;}
    return 0;
}
template <class T>
void compress(vector <T> &v) {
    sort(ALL(v));
    v.erase(unique(ALL(v)), (v).end());
}

void add(int &a, int b) {   a += b; if (a >= mod)   a -= mod;   }
void sub(int &a, int b) {   a -= b; if (a <  0)     a += mod;   }
int sz[maxn];
bool is_centroid[maxn];
vector<pi> adj[maxn];
int root = 0, n, k;
int ans = 1e9, dp[maxn];
int mx = 0;
const int N = 1e6 + 1;
struct Segment{
    int n;
    vector<int> t, del;
    Segment(int _n = 0){
        n = _n;
        t.resize(4 * n + 1);
        del.resize(4 * n + 1);
    }
    void down(int id, int l, int r){
        if(del[id]){
            t[id * 2] = 1e9; t[id * 2 + 1] = 1e9;
            del[id * 2] = del[id]; del[id * 2 + 1] = del[id];
            del[id] = 0;
        }
    }
    void update(int id, int l, int r, int pos, int val){
        if(pos > r | pos < l) return;
        if(l == r){
            t[id] = min(t[id], val);
            return;
        }
        down(id, l, r);
        int mid = l + r >> 1;
        update(id << 1, l, mid, pos, val);
        update(id * 2 + 1, mid + 1, r, pos, val);
        t[id] = min(t[id << 1], t[id * 2 + 1]);
    }
    void Clear(int id, int l, int r, int u, int v){
        if(v < l || u > r) return;
        if(u <= l || v >= r){
            t[id] = 1e9;
            del[id] = 1;
            return;
        }
        down(id, l, r);
        int mid = l + r >> 1;
        Clear(id << 1, l, mid, u, v);
        Clear(id * 2 + 1, mid + 1, r, u, v);
        t[id] = min(t[id << 1], t[id * 2 + 1]);
    }
    int get(int id, int l, int r, int u, int v){
        if(v < l || u > r) return 1e9;
        if(l >= u && r <= v) return t[id];
        int mid = l + r >> 1;
        down(id, l, r);
        return min(get(id << 1, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
    }
};
Segment f;
void get(int u, int pa, int h, int val){
    if(h > k) return;
    int tmp = f.get(1, 1, N, k - h + 1, k - h + 1);
    ans = min(ans, tmp + val);
    for(pi v : adj[u]) if(v.fi != pa && !is_centroid[v.fi]){
        get(v.fi, u, h + v.se, val + 1);
    }
}
void update(int u, int pa, int h, int val){
    if(h > k) return;
    f.update(1, 1, N, h + 1, val);
    maximize(mx, h);
    for(pi v : adj[u]) if(v.fi != pa && !is_centroid[v.fi]){
        update(v.fi, u, h + v.se, val + 1);
    }
}

void dfs(int u, int pa){
    sz[u] = 1;
    for(pi v : adj[u]) if(v.fi != pa && !is_centroid[v.fi]){
        dfs(v.fi, u); sz[u] += sz[v.fi];
    }
}
int Find_Centroid(int u, int Size, int pa){
    for(pi v : adj[u]){
        if(v.fi != pa && sz[v.fi] > Size / 2 && !is_centroid[v.fi]){
            return Find_Centroid(v.fi, Size, u);
        }
    }
    return u;
}
void Build_Centroid(int u, int pa){
    dfs(u, -1);
    int centroid = Find_Centroid(u, sz[u], -1);
    is_centroid[centroid] = true;
//-----------------------------------------
    f.Clear(1, 1, N, 1, N);
    f.update(1, 1, N, 1, 0);
    mx = 0;
    for(pi v : adj[centroid]){
        if(!is_centroid[v.fi]){
            get(v.fi, centroid, v.se, 1);
            update(v.fi, centroid, v.se, 1);
        }
    }
//    f.Clear(1, 1, N, 1, mx + 1);
//-----------------------------------------
    for(pi v : adj[centroid]){
        if(!is_centroid[v.fi]){
            Build_Centroid(v.fi, centroid);
        }
    }
}
int best_path(int _N, int K, int H[][2], int L[]){
    n = _N; k = K;
    f = Segment(N);
    fis(i, 0, n - 2){
        adj[H[i][0] + 1].pb({H[i][1] + 1, L[i]});
        adj[H[i][1] + 1].pb({H[i][0] + 1, L[i]});
    }
    Build_Centroid(1, -1);
    if(ans >= 1e9 - 1) return -1;
    return ans;
}

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