Submission #1107467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107467		SoMotThanhXuan	Race (IOI11_race)	C++17	100 / 100	368 ms	66204 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define left _________left
#define right _________right
#define NAME ""
const int mod = 1e9 + 7;
bool maximize(int &u, int v){
    if(v > u){
        u = v;
        return true;
    }
    return false;
}
bool minimize(int &u, int v){
    if(v < u){
        u = v;
        return true;
    }
    return false;
}
bool maximizell(long long &u, long long v){
    if(v > u){
        u = v;
        return true;
    }
    return false;
}
bool minimizell(long long &u, long long v){
    if(v < u){
        u = v;
        return true;
    }
    return false;
}
int fastPow(int a, int n){
    if(n == 0) return 1;
    int t = fastPow(a, n >> 1);
    t = 1ll * t * t % mod;
    if(n & 1) t = 1ll * t * a % mod;
    return t;
}
void add(int &u, int v){
    u += v;
    if(u >= mod) u -= mod;
}
void sub(int &u, int v){
    u -= v;
    if(u < 0) u += mod;
}
const int maxN = 2e5 + 5;
const int maxK = 1e6 + 5;
const int INF = 1e9;
vector<pair<int, int>> adj[maxN];
int n, m, k;
int answer = INF, sz[maxN], in[maxN], out[maxN], timeDFS, id[maxN], heavy[maxN], depth[maxN];
int high[maxN];
map<int, int> Min;
inline void dfs(int u){
    in[u] = ++timeDFS;
    id[timeDFS] = u;
    sz[u] = 1;
    for(auto[v, w] : adj[u]){
        if(in[v])continue;
        high[v] = high[u] + 1;
        depth[v] = depth[u] + w;
        dfs(v);
        sz[u] += sz[v];
        if(sz[v] > sz[heavy[u]]) heavy[u] = v;
    }
    out[u] = timeDFS;
}
inline void hld(int u = 1, int pre = 0, bool keep = true){
    for(auto[v, w] : adj[u])if(v != heavy[u] && v != pre){
        hld(v, u, false);
//        cout << "erase ";
//        cout << v << "\n";
        FOR(i, in[v], out[v]){
//            cout << id[i] << ' ' << depth[id[i]] << "\n";
            Min.erase(depth[id[i]]);
        }
    }
    if(heavy[u]) hld(heavy[u], u, true);
    if(Min.find(depth[u]) == Min.end()) Min[depth[u]] = high[u];
    else minimize(Min[depth[u]], high[u]);
//    cout << u << "\n";
//    cout << answer << ' ';
    if(Min.find(k + depth[u]) != Min.end()) minimize(answer, Min[depth[u] + k] - high[u]);
//    cout << answer;
//    cout << "\n";
    for(auto[v, w] : adj[u]){
        if(v != heavy[u] && v != pre){
            FOR(i, in[v], out[v]){
                int c = id[i], tmp = depth[c] - 2 * depth[u];
                if(Min.find(k - tmp) != Min.end()){
//                    cout << u << ' ' << c << " " << depth[c] << ' ' << depth[u] << ' ' << tmp << '\n';
//                    cout << Min[k - tmp] << "\n";
//                    cout << answer << ' ';
                    minimize(answer, high[c] - 2 * high[u] + Min[k - tmp]);
//                    cout << answer << "\n";
                }
            }
            FOR(i, in[v], out[v]){
                if(Min.find(depth[id[i]]) == Min.end()) Min[depth[id[i]]] = high[id[i]];
                else minimize(Min[depth[id[i]]], high[id[i]]);
            }
        }
    }
}
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 u = H[i][0], v = H[i][1], w = L[i];
        ++u;
        ++v;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    dfs(1);
    hld();
    return answer == INF ? -1 : answer;
}
//int H[maxN][2], L[maxN];
//inline void solve(){
//    cin >> n >> k;
//    FOR(i, 0, n - 2){
//        int u, v, w;
//        cin >> u >> v >> w;
//        H[i][0] = u;
//        H[i][1] = v;
//        L[i] = w;
//
//    }
//    cout << best_path(n, k, H, L);
//}
//int main(){
//    if(fopen(NAME".inp", "r")){
//        freopen(NAME".inp", "r", stdin);
//        freopen(NAME".out", "w", stdout);
//    }
//    ios_base::sync_with_stdio(false);
//    cin.tie(0);
//    cout.tie(0);
//
//    int t = 1;
////    cin >> t;
//    while(t--){
//        solve();
//    }
//    return 0;
//}

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