Submission #720166

#	Time	Username	Problem	Language	Result	Execution time	Memory
720166		marvinthang	Race (IOI11_race)	C++17	100 / 100	405 ms	36124 KiB

race

/******************************
*    author : @marvinthang    *
*    date : 15 / 01 / 2022    *
******************************/
 
#include "race.h"
#include <bits/stdc++.h>
 
using namespace std;
 
#define  superspeed  ios_base::sync_with_stdio(false); cin.tie(nullptr); //cout.tie(nullptr);
#define  file(name)  if (fopen (name".inp", "r") ) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
#define REP(i, a, b)  for (__typeof(a) i = (a) - ((a) > (b)); i != (b) - ((a) > (b)); i += ((a) > (b) ? -1 : 1))
#define FOR(i, a, b)  for (__typeof(a) i = (a); i != (b) + ((a) > (b) ? -1 : 1); i += ((a) > (b) ? -1 : 1))
 
template <class U, class V> ostream & operator << (ostream& out, const pair<U, V> &p) { return out << '(' << p.first << ", " << p.second << ')'; }
template <class T> ostream & operator << (ostream &out, const vector<T> &vt) { out << '{'; for (size_t i = 0; i + 1 < vt.size(); i++) out << vt[i] << ", "; if (!vt.empty()) out << vt.back(); return out << '}'; }
void minimize(int &a, int b) { if (a > b) a = b; }
const       int MOD = 1e9 + 7;
const     double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const     int dir[] = {0, 1, 0, -1, 0}; // {0, 1, 1, -1, -1, 1, 0, -1, 0};
const  long long oo = 1e18;
const       int MAX = 2e5 + 5;
 
int N, K;
vector <pair <int, int>> adj[MAX];
int minPath[MAX * 10], newPath[MAX * 5], res;
vector <int> save, save2;
bool used[MAX];
 
void calc(int u, int par, int depth, int weight) {
    if (weight > K) return;
    res = min(res, minPath[K - weight] + depth);
    newPath[weight] = min(newPath[weight], depth);
    save.push_back(weight);
    save2.push_back(weight);
    for (pair <int, int> &x: adj[u]) {
        int v = x.second, w = x.first;
        if (v == par || used[v]) continue;
        calc(v, u, depth + 1, weight + w);
    }
}
 
int sizes[MAX];
 
int calcSize(int u, int par) {
    sizes[u] = 1;
    for (pair <int, int> &x: adj[u]) {
        int v = x.second;
        if (v == par || used[v]) continue;
        sizes[u] += calcSize(v, u);
    }
    return sizes[u];
}
 
int findCentroid(int u, int par, int n) {
    for (pair <int, int> &x: adj[u]) {
        int v = x.second;
        if (v == par || used[v]) continue;
        if (sizes[v] > n / 2) return findCentroid(v, u, n);
    }
    return u;
}
 
void solve(int u) {
    int n = calcSize(u, 0);
    int centroid = findCentroid(u, 0, n);
    used[centroid] = true;
    save.clear();
    for (pair <int, int> &x: adj[centroid]) {
        int v = x.second, w = x.first;
        if (used[v]) continue;
        calc(v, centroid, 1, w);
        for (int &x: save2) {
            minPath[x] = min(minPath[x], newPath[x]);
            newPath[x] = N + 1;
        }
        save2.clear();
    }
    res = min(res, minPath[K]);
    for (int &x: save) minPath[x] = N + 1;
    for (pair <int, int> &x: adj[centroid]) {
        int v = x.second;
        if (!used[v]) solve(v);
    }
}
 
int best_path(int n, int k, int h[][2], int l[]) {
    N = n; K = k;
    for (int i = 0; i < N - 1; ++i) {
        int u = h[i][0], v = h[i][1], w = l[i];
        ++u; ++v;
        adj[u].push_back( make_pair(w, v) );
        adj[v].push_back( make_pair(w, u) );
    }
    res = 1e9;
    fill(minPath, minPath + 1 + K, N + 1);
    fill(newPath, newPath + 1 + K, N + 1);
    solve(1);
    if (res > N) res = -1;
    return res;
}

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