Submission #530108

#	Time	Username	Problem	Language	Result	Execution time	Memory
530108		buidangnguyen05	Race (IOI11_race)	C++14	100 / 100	456 ms	36804 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rnd(long long l, long long r)
{
    return l + rng() % (r - l + 1);
}
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
    cerr << *it << " = " << a << endl;
    err(++it, args...);
}
#define debug(x) cerr << #x << " is " << x << "\n";
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define gg exit(0)
#define yn(x) ((x==true)?"YES":"NO")
#define getbit(x,i) ((x>>(i-1))&1)
#define batbit(x,i) (x|(1ll<<(i-1)))
#define tatbit(x,i) (x&~(1<<(i-1)))
//#define int long long
//#define DEBUG
const int N = 2e5 + 10, K = 1e6 + 10;
int dd[N], sz[N], avail[K], min_path[K], curr_node, n, k, res = 1e8;
vector<ii> adj[N];
int calc(int x, int par)
{
    sz[x] = 1;
    forv(i, adj[x]) if (!dd[i.fi] && i.fi != par) sz[x] += calc(i.fi, x);
    return sz[x];
}
int get_ctr(int x, int par, int cnt)
{
    forv(i, adj[x]) if (!dd[i.fi] && i.fi != par && sz[i.fi] * 2 > cnt) return get_ctr(i.fi, x, cnt);
    return x;
}
void dfs_ans(int x, int par, int curr_w,  int curr_len)
{
    if (curr_w > k) return;
    if (avail[k - curr_w] == curr_node) res = min(res, curr_len + min_path[k - curr_w]);
    if (curr_w == k) res = min(res, curr_len);
    forv(i, adj[x]) if (!dd[i.fi] && i.fi != par) dfs_ans(i.fi, x, curr_w + i.se, curr_len + 1);
}
void dfs_upd(int x, int par, int curr_w, int curr_len)
{
    if (curr_w > k) return;
    if (avail[curr_w] != curr_node)
    {
        avail[curr_w] = curr_node;
        min_path[curr_w] = curr_len;
    }
    else min_path[curr_w] = min(min_path[curr_w], curr_len);
    forv(i, adj[x]) if (!dd[i.fi] && i.fi != par) dfs_upd(i.fi, x, curr_w + i.se, curr_len + 1);
}
void centroid(int x, int par = 0)
{
    curr_node++;
    int cnt = calc(x, x); int node = get_ctr(x, x, cnt);
    dd[node] = 1;
    forv(i, adj[node]) if (!dd[i.fi])
    {
        dfs_ans(i.fi, node, i.se, 1);
        dfs_upd(i.fi, node, i.se, 1);
    }
    forv(i, adj[node]) if (!dd[i.fi]) centroid(i.fi, node);
}
int best_path(int _n, int _k, int H[][2], int L[]) {
    n = _n; k = _k;
    for (int i = 1; i < n; ++i) {
        adj[H[i - 1][0]].push_back(make_pair(H[i - 1][1], L[i - 1]));
        adj[H[i - 1][1]].push_back(make_pair(H[i - 1][0], L[i - 1]));
    }
    centroid(1);
    return ((res == 1e8) ? -1 : res);
}

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