Submission #1093107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093107		anhthi	Race (IOI11_race)	C++14	0 / 100	2 ms	12636 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;

#define fi first
#define se second
#define ll long long
#define mp(x, y) make_pair(x, y)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define pb push_back
#define max_rng *max_element
#define min_rng *min_element
#define rep(i, n) for(int i = 1, _n = (n); i <= _n; ++i)
#define forn(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define ford(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)

template <class X, class Y>
    inline bool maximize(X &x, Y y) {
        return (x < y ? x = y, true : false);
    }

template <class X, class Y>
    inline bool minimize(X &x, Y y) {
        return (x > y ? x = y, true : false);
    }

template <class X>
    inline void compress(vector<X> &a) {
        sort(all(a));
        a.resize(unique(all(a)) - a.begin());
    }

int ctz(ll x) { return __builtin_ctzll(x); }
int lg(ll x) { return 63 - __builtin_clzll(x); }
int popcount(ll x) { return __builtin_popcount(x); }

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) {
    return l + abs((ll) rng()) % (r - l + 1);
}

const ll oo = (ll) 1e17;
const int inf = (ll) 2e9 + 7, mod = (ll) 1e9 + 7;

const int mxn = 3e5 + 5, mxm = 3e2 + 5;
const int LG = 18, BASE = 311, BLOCK = 350;

void add(int &x, int y) { x += y; if (x >= mod) x -= mod; }
void sub(int &x, int y) { x -= y; if (x < 0) x += mod; }

int n, k;
ll w[mxn];
vector<pair<int, int>> g[mxn];

bool del[mxn];
int childs[mxn];
int getSz(int u, int p) {
    childs[u] = 1;
    for (auto &[v, i] : g[u]) if (v != p && !del[v]) {
        childs[u] += getSz(v, u);
    }
    return childs[u];
}

int getCen(int u, int p, int sz) {
    for (auto &[v, i] : g[u]) if (v != p && !del[v]) {
        if (2 * childs[v] > sz) return getCen(v, u, sz);
    }
    return u;
}

int ans = inf;
map<ll, int> mp;

void dfs(int u, int p, bool flag, ll dist, int d = 1) {
    if (dist > k) return;
    if (flag) {
        if (mp.find(k - dist) != mp.end()) {
            minimize(ans, mp[k - dist] + d);
        }
    }
    else {
        if (mp.find(dist) == mp.end())
            mp[dist] = d;
        else minimize(mp[dist], d);
    }

    for (auto &[v, i] : g[u]) if (v != p && !del[v])
        dfs(v, u, flag, dist + w[i], d + 1);

    return;
}

void solve(int root) {
    mp.clear();

    mp[0] = 0;
    for (auto &[v, i] : g[root]) if (v != root && !del[v]) {
        dfs(v, root, 0, w[i]);
        dfs(v, root, 1, w[i]);
    }

    return;
}

void dnc(int u) {
    int sz = getSz(u, 0);
    int cen = getCen(u, 0, cen);

    solve(cen);

    del[cen] = true;
    for (auto &[v, i] : g[cen]) if (!del[v])
        dnc(v);
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N; k = K;
    forn(i, 0, n - 2) {
        int u = H[i][0];
        int v = H[i][1];
        u++; v++;
        g[u].pb(mp(v, i));
        g[v].pb(mp(u, i));
    }
    forn(i, 0, n - 2) w[i] = L[i];

    dnc(1);

    return (ans == inf ? -1 : ans);
}

//int main(void) {
//
//    ios_base::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//
//    #define TASK "cquery"
//    if (fopen(TASK".inp", "r")) {
//        freopen(TASK".inp", "r", stdin);
//        freopen(TASK".out", "w", stdout);
//    }
//
//    int a[][2] = {{0, 1}, {1, 2}, {1, 3}};
//    int b[] = {1, 2, 4};
//    best_path(4, 3, a, b);
//
//    return 0;
//}

Compilation message (stderr)

race.cpp: In function 'int getSz(int, int)':
race.cpp:63:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |     for (auto &[v, i] : g[u]) if (v != p && !del[v]) {
      |                ^
race.cpp: In function 'int getCen(int, int, int)':
race.cpp:70:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |     for (auto &[v, i] : g[u]) if (v != p && !del[v]) {
      |                ^
race.cpp: In function 'void dfs(int, int, bool, long long int, int)':
race.cpp:92:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   92 |     for (auto &[v, i] : g[u]) if (v != p && !del[v])
      |                ^
race.cpp: In function 'void solve(int)':
race.cpp:102:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |     for (auto &[v, i] : g[root]) if (v != root && !del[v]) {
      |                ^
race.cpp: In function 'void dnc(int)':
race.cpp:117:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  117 |     for (auto &[v, i] : g[cen]) if (!del[v])
      |                ^
race.cpp:111:9: warning: unused variable 'sz' [-Wunused-variable]
  111 |     int sz = getSz(u, 0);
      |         ^~
race.cpp:112:21: warning: 'cen' is used uninitialized in this function [-Wuninitialized]
  112 |     int cen = getCen(u, 0, cen);
      |               ~~~~~~^~~~~~~~~~~

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