Submission #498172

#	Time	Username	Problem	Language	Result	Execution time	Memory
498172		XII	Race (IOI11_race)	C++17	21 / 100	3070 ms	38752 KiB

race

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

using ll = long long;

#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)

//#define IOS cin.tie(0)->sync_with_stdio(false);
//#define PROB "IOI11_race"
//void Fi(){
//    if(fopen(PROB".inp", "r")){
//        freopen(PROB".inp", "r", stdin);
//        freopen(PROB".out", "w", stdout);
//    }
//}

const int INF = 1e9;
const int limN = 2e5 + 1;
const int limK = 1e6 + 1;
int n, k;
using pi = pair<int, int>;
//vector<pi> adj[N];
//multiset<pi> s[N];

int ans = INF;
//void dfs(int u, int p = -1){
//    s[u].insert({0, 0});
//    for(auto [w, v]: adj[u]) if(v != p){
//        dfs(v, u);
//        for(auto p: s[v]) if(p.fi + w <= k){
//            s[u].insert({p.fi + w, p.se + 1});
//        } else break;
//    }
//    for(auto [w, v]: adj[u]) if(v != p){
//        for(auto p: s[v]) if(p.fi + w <= k){
//            s[u].erase(s[u].find({p.fi + w, p.se + 1}));
//        } else break;
//        for(auto p: s[v]) if(p.fi + w <= k){
//            auto it = s[u].lower_bound({k - (p.fi + w), -1});
//            if(it == s[u].end()) continue;
//            if((*it).fi == k - (p.fi + w)){
//                ans = min(ans, p.se + 1 + (*it).se);
//            }
//        } else break;
//        for(auto p: s[v]) if(p.fi + w <= k){
//            s[u].insert({p.fi + w, p.se + 1});
//        } else break;
//    }
//}

int sz[limN];
set<pi> G[limN];

int dfsSize(int u, int p = -1){
    sz[u] = 1;
    for(auto [w, v]: G[u]) if(v != p){
        sz[u] += dfsSize(v, u);
    }
    return sz[u];
}

int centroid(int u, int p, int n){
    for(auto [w, v]: G[u]) if(v != p){
        if(sz[v] > n / 2) return centroid(v, u, n);
    }
    return u;
}

multiset<pi> s[limN];
void dfs(int u, int p){
    s[u].insert({0, 0});
    for(auto [w, v]: G[u]) if(v != p){
        dfs(v, u);
        for(auto x: s[v]) if(x.fi + w <= k){
            s[u].insert({x.fi + w, x.se + 1});
        } else break;
        s[v].clear();
    }
//    cout << u << ": ";
//    for(auto x: s[u]) cout << "{" << x.fi << ", " << x.se << "} ";
//    cout << "\n";
}

int best_path(int N, int K, int H[][2], int L[]){
    n = N, k = K;
//    FOR(i, 0, N - 1){
//        adj[H[i][0]].eb(L[i], H[i][1]);
//        adj[H[i][1]].eb(L[i], H[i][0]);
//    }
    FOR(i, 0, N - 1){
        G[H[i][0]].insert({L[i], H[i][1]});
        G[H[i][1]].insert({L[i], H[i][0]});
    }

    queue<int> qe;
    qe.emplace(0);
    while(!qe.empty()){
        int u = qe.front(); qe.pop();
        int n = dfsSize(u);
        int c = centroid(u, -1, n);
        s[c].insert({0, 0});
        for(auto [w, v]: G[c]){
            dfs(v, c);

            for(auto x: s[v]) if(x.fi + w <= k){
                s[c].insert({x.fi + w, x.se + 1});
            } else break;
        }
        for(auto [w, v]: G[c]){
            for(auto x: s[v]) if(x.fi + w <= k){
                s[c].erase(s[c].find({x.fi + w, x.se + 1}));
            } else break;
            for(auto x: s[v]) if(x.fi + w <= k){
                auto it = s[c].lower_bound({K - (x.fi + w), -1});
                if(it == s[c].end()) continue;
                if((*it).fi == K - (x.fi + w)){
                    ans = min(ans, x.se + 1 + (*it).se);
                }
            } else break;
            for(auto x: s[v]) if(x.fi + w <= k){
                s[c].insert({x.fi + w, x.se + 1});
            } else break;
            s[v].clear();
        }
        s[c].clear();
        vector<pi> tmp(ALL(G[c]));
        for(auto [w, v]: tmp){
            G[c].erase({w, v});
            G[v].erase({w, c});
            qe.emplace(v);
        }
    }

//    dfs(0);
    if(ans != INF) return ans;
    return -1;
}

//int N, K, H[limN][2], L[limN];
//
//int main(){
//    IOS;
//    Fi();
//    cin >> N >> K;
//    FOR(i, 0, N - 1){
//        cin >> H[i][0] >> H[i][1];
//    }
//    FOR(i, 0, N - 1) cin >> L[i];
//    cout << best_path(N, K, H, L);
//    return 0;
//}

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