Submission #672402

#	Time	Username	Problem	Language	Result	Execution time	Memory
672402		vjudge1	Race (IOI11_race)	C++17	100 / 100	1530 ms	71804 KiB

race

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ld long double
#define el "\n"
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;

const ll N = 1e6 + 7;
const ll mod = 1e9 + 7;
int dx[] = {0, -1, 0, 1, -1, 1, -1, 1};
int dy[] = {-1, 0, 1, 0, 1, -1, -1, 1};
ll n, m, k, y, x, l, r;
vector<pair<int, ll>> adj[N];
int sz[N], dad[N];
bool vis[N];
map<ll, int> mn;
map<ll, int> cnt;
int ans = 1e9;

int dfs_sz(int node, int par) {
    sz[node] = 1;
    for (auto j: adj[node]) {
        if (j.first == par || vis[j.first]) {
            continue;
        }
        sz[node] += dfs_sz(j.first, node);
    }
    return sz[node];
}

int dfs_cen(int node, int par, int ch) {
    for (auto j: adj[node]) {
        if (sz[j.first] > ch / 2 && !vis[j.first] && j.first != par) {
            return dfs_cen(j.first, node, ch);
        }
    }
    return node;
}

vector<pair<ll, int>> pool;

void dfs_coll(int node, int par, ll dis, int cur) {
    pool.push_back({dis, cur});
    for (auto j: adj[node]) {
        if (vis[j.first] || j.first == par) {
            continue;
        }
        dfs_coll(j.first, node, dis + j.second, cur + 1);
    }
}

void build(int node, int par) {
    int sz = dfs_sz(node, par);
    int cen = dfs_cen(node, par, sz);
    if (par == -1) {
        par = cen;
    }
    vis[cen] = 1;
    cnt[0] = 1;
    for (auto j: adj[cen]) {
        if (vis[j.first]) {
            continue;
        }
        pool.clear();
        dfs_coll(j.first, cen, j.second, 1);
        for (auto l: pool) {
            if (l.first <= k) {
                if (mn[k - l.first] || l.first == k) {
                    ans = min(ans, l.second + mn[k - l.first]);
                }
            }
        }
        for (auto l: pool) {
            if (!mn[l.first]) {
                mn[l.first] = l.second;
            }
            mn[l.first] = min(mn[l.first], l.second);
        }
    }
    mn.clear();
    for (auto j: adj[cen]) {
        if (vis[j.first]) {
            continue;
        }
        build(j.first, cen);
    }
    return;
}
int best_path(int N,int K,int H[][2],int L[])
{
    k=K;
n=N;
    for (int i=0;i<n-1;i++)
    {
        adj[H[i][0]].push_back({H[i][1],L[i]});
        adj[H[i][1]].push_back({H[i][0],L[i]});
    }
    build(0,-1);
    if (ans==1e9)
    {
        ans=-1;
    }
    return ans;
}
//void dowork() {
//    cin >> n >> k;
//    int w;
//    for (int i = 1; i < n; i++) {
//        cin >> x >> y >> w;
//        adj[x].push_back({y, w});
//        adj[y].push_back({x, w});
//    }
//    build(0, -1);
//    if (ans == 1e9) {
//        ans = -1;
//    }
//    cout << ans << el;
//}
//
//int main() {
//    fast
//    //freopen("barnparinting.in","r",stdin);
//    //freopen("barnparinting.out","w",stdout);
//    int t = 1;
//    //cin >> t;
//    for (int i = 1; i <= t; i++) {
//        dowork();
//    }
//}

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