Submission #1156101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156101		gulmix	Race (IOI11_race)	C++20	0 / 100	3 ms	5972 KiB

race

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define oset tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> 

const int N = 2e5 + 5;
vector<pair<int, int>> graph[N];
vector<pair<int, int>> res;
int k, sz[N], used[N];
int ans = 1e9;

void dfs(int v, int p){
    sz[v] = 1;
    for(auto &[u, w]: graph[v]){
        if(u == p || used[u])continue;
        dfs(u, v);
        sz[v] += sz[u];
    }
}

int get(int v, int p, int psz){
    for(auto &[u, w]: graph[v]){
        if(u != p && !used[u] && 2*sz[u] > psz)return get(u, v, psz);
    }
    return v;
}

void solve(int v, int p, int s, int cnt){
    if(s > k || cnt > ans){
        return;
    }
    res.push_back({s, cnt});
    for(auto &[u, w]: graph[v]){
        if(u == p || used[u])continue;
        solve(u, v, s + w, cnt+1);
    }
}

void decompose(int v){
    dfs(v, -1);
    v = get(v, -1, sz[v]);
    used[v] = 1;
    map<int, int> ps;
    for(auto &[u, w]: graph[v]){
        if(used[u])continue;
        solve(u, v, w, 1);
        for(auto &i: res){
            if(ps.find(k - i.first) != ps.end()){
                ans = min(ans, ps[k - i.first] + i.second);
            }else if(i.first == k){
                ans = min(ans, i.second);
            }
        }
        for(auto &i: res){
            if(ps.find(i.first) == ps.end()){
                ps[i.first] = i.second;
            }else{
                ps[i.first] = min(ps[i.first], i.second);
            }
        }
        res.clear();
    }
    for(auto &[u, w]: graph[v]){
        if(!used[u])decompose(u);
    }
}

int best_path(int n, int _, int h[][2], int l[]){
    k = _;
    for(int i = 0; i < n-1; i++){
        graph[h[i][0]].push_back({h[i][1], l[i]});
        graph[h[i][1]].push_back({h[i][0], l[i]});
    }
    memset(used, 0, sizeof used);
    decompose(0);
    return ans == -1e18 ? -1 : ans;
}

//int main(){
//    ios::sync_with_stdio(false);
//    cin.tie(0); 
//    //ifstream cin("inputf.txt");
//    //ofstream cout("outputfv.txt");
//    ll n; cin >> n;
//    string s; cin >> s;
//    vector<vector<ll>> dp(n, vector<ll>(n, 1e9));
//    for(int i = n-1; i >= 0; i--){
//        for(int j = 0; j < n; j++){
//            if(i > j)dp[i][j] = 0;
//            else if(i == j)dp[i][j] = 1;
//            else{
//                dp[i][j] = dp[i+1][j] + 1;
//                for(int k = i + 1; k <= j; k++){
//                    if(s[i] == s[k]){
//                        dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k][j]);
//                    }
//                }
//            }
//        }
//    }
//    cout << dp[0][n-1];
//}

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