Submission #1239318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239318		Minbaev	Race (IOI11_race)	C++20	21 / 100	3093 ms	15688 KiB

race

 #include "race.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define pb      push_back
#define all(x)  x.begin(),x.end()
#define ar      array
#define mrand(a, b)   uniform_int_distribution<int>(a, b)(rng)

template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}

template<class T> using ste = tree<T, null_type, less_equal<T>,
rb_tree_tag, tree_order_statistics_node_update>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

namespace FAST {
    template<typename T, typename F>
    istream &operator>>(istream &cin, pair<T, F> &p) {
        cin >> p.first >> p.second;
        return cin;
    }

    template<typename T, typename F>
    ostream &operator<<(ostream &cout, pair<T, F> &p) {
        cout << p.first << ' ' << p.second;
        return cout;
    }

    template<typename T>
    istream &operator>>(istream &cin, vector<T> &a) {
    for (T &i: a) cin >> i;
        return cin;
    }

    template<typename T>
    ostream &operator<<(ostream &cout, vector<T> &a) {
          for (T i: a) cout << i << ' ';
        return cout;
    }

    template<typename T>
    istream &operator>>(istream &cin, deque<T> &a) {
        for (T &i: a) cin >> i;
        return cin;
    }

    template<typename T>
    ostream &operator<<(ostream &cout, deque<T> &a) {
        for (T i: a) cout << i << ' ';
        return cout;
    }
}
using namespace FAST;

const long long inf = 1e17 + 7;
const int mod = 1e9 + 7;
const int md = 998244353;

int n,m,k;
basic_string<ar<int,2>>g[200005];
vector<int> sz(200005), vis(200005), cnt(1000005, mod);
int res = mod;
int mx = 0;

void dfs_sz(int x, int pr){
    sz[x] = 1;

    for(auto [to, cost] : g[x]){
        if(to == pr)continue;
        dfs_sz(to, x);
        sz[x] += sz[to];
    }
}

int fc(int x, int pr, int siz){
    for(auto [to, cost]:g[x]){
        if(to == pr || vis[to])continue;
        if(sz[to] > siz)return fc(to, x, siz);
    }
    return x;
}

void dfs(int x, int pr, int dist, int cont, bool flag){
    // cout << x << " " << pr << " " << dist << " " << cont << " " << flag << "\n";
    if(!flag){
        // if(cnt[k-dist] > 0)
        umin(res, cont + cnt[k - dist]);
    }
    else
        umin(cnt[dist], cont);
    umax(mx, dist);

    for(auto [to, cost] : g[x]){
        if(vis[to] || pr == to)continue;
        if(dist + cost > k)continue;
        dfs(to, x, dist + cost, cont + 1, flag);
    }
}

void dec(int x){
    dfs_sz(x, -1);
    int cen = fc(x, -1, sz[x] / 2);
    // cout << cen << "\n";
    vis[cen] = 1;
    cnt[0] = 0;
    mx = 0;

    for(auto [to, cost] : g[cen]){
        if(vis[to] || cost > k)continue;
        dfs(to, cen, cost, 1, false);
        dfs(to, cen, cost, 1, true);
    }
    // cout << cnt[1] << "\n";

    for(int i = 0;i<=mx;i++){
        cnt[i] = mod;
    }
    // exit(0);
    for(auto [to, cost] : g[cen]){
        if(vis[to])continue;
        dec(to);
    }

}

int best_path(int N, int K, int H[][2], int L[]){

    for(int i = 1;i<N;i++){
        g[H[i-1][0]].pb({H[i-1][1], L[i-1]});
        g[H[i-1][1]].pb({H[i-1][0], L[i-1]});
    }

    k = K;

    dec(0);

    if(res == mod)res = -1;
    // cout << res << "\n";
    return res;
}

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