Submission #766566

#	Time	Username	Problem	Language	Result	Execution time	Memory
766566		Mahmoud_Atia	Race (IOI11_race)	C++14	0 / 100	14 ms	27732 KiB

race

#include <bits/stdc++.h>
#include "race.h"
typedef long double ld;
typedef long long ll;
using namespace std;
int di[] = {1, 0, -1, 0};
int dj[] = {0, 1, 0, -1};
const ll oo = 1e18, MOD = 1e9 + 7;
const int N = 1e6 + 5, M = 1e6 + 5;
const ld PI = acos(-1.0), EPS = 1e-9;

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int t, n, m, k, a[N], sz[N], tmp[N], mx, l[N], r[N];
vector<pair<int, int>> v[N];
bool vis[N];
int ans = 1e9;

int get_subtree_sizes(int node, int p = -1) {
    sz[node] = 1;
    for (auto x:v[node]) if (x.first != p && !vis[x.first]) sz[node] += get_subtree_sizes(x.first, node);
    return sz[node];
}

int get_centroid(int node, int size, int p = -1) {
    for (auto x:v[node]) {
        if (x.first == p || vis[x.first]) continue;
        if (sz[x.first] >= size) return get_centroid(x.first, size, node);
    }
    return node;
}


bool y;

void get_cnt(int node, int p, int yes, int sum, int level) {
    if (sum > k) return;
    if (sum == k) ans = min(ans, level);
    if (yes == 1) tmp[sum] = min(tmp[sum], level);
    else if (yes) tmp[sum] = 1e9;
    else ans = min(ans, level + tmp[k - sum]);
    for (auto x:v[node]) if (x.first != p && !vis[x.first]) get_cnt(x.first, node, yes, sum + x.second, level + 1);
}

void centroid_decomp(int node = 0) {
    get_subtree_sizes(node);
    int c = get_centroid(node, sz[node] / 2);
    vis[c] = 1;
    if (c == 6) y = 1;
    else y = 0;
    mx = 0;
    for (auto x:v[c]) if (!vis[x.first]) get_cnt(x.first, c, 0, x.second, 1), get_cnt(x.first, c, 1, x.second, 1);
    for (auto x:v[c]) if (!vis[x.first]) get_cnt(x.first, c, 2, x.second, 1);
    for (auto x:v[c]) if (!vis[x.first]) centroid_decomp(x.first);
}


//#define endl '\n'
int best_path(int N, int K, int H[][2], int L[]) {
    //ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //freopen("marsllino.in", "r", stdin);
    //memset(dp, -1, sizeof dp);
    fill(tmp, tmp + 1000000 + 5, 1e9);
    n = N, k = K;
    for (int i = 1; i < n; i++) {
        v[H[i][1]].push_back({H[i][0], L[i]});
        v[H[i][0]].push_back({H[i][1], L[i]});
    }
    centroid_decomp();
    cout << (ans == 1e9 ? -1 : ans);
    return 0;
}

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