Submission #1294302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294302		mutammim	경주 (Race) (IOI11_race)	C++20	21 / 100	330 ms	31724 KiB

race

#include<bits/stdc++.h>
using namespace std;

// Extra functionality :
// *st.find_by_order(index) = value at index
// st.order_of_key(value) = number of elements strictly less than value

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

#define ll long long
#define lld long double
#define vll vector<long long>
#define pll pair<long long, long long>
#define vvll vector<vll>
#define vvvll vector<vvll>
#define ar array
#define F first
#define S second

#define all(v) v.begin(),v.end()
#define range(v, i, j) v.begin()+i, v.begin()+j+1
#define For(i, a, b) for(long long i = (a); i <= (b); ++(i))
#define L(i, a, b) for(long long i = (a); i <= (b); ++(i))
#define R(i, a, b) for(long long i = (a); i >= (b); --(i))
#define sz(x) (ll)(x.size())
#define extract(m, x) { auto it = (m).find(x); if (it != (m).end()) (m).erase(it); } // set, multiset, map
#define gp " "
#define nl "\n"
#define yes cout<<"YES"<<nl
#define no cout<<"NO"<<nl

#define isSet(x, i) ((x>>i)&1)
#define setbit(x, i) (x | (1LL<<i))
#define resetbit(x, i) (x & (~(1LL << i)))
#define toggleBit(x, i) ((x) ^ (1LL << (i)))
#define getBit(x, i) (((x) >> (i)) & 1)
#define clz(x) __builtin_clzll(x)
#define ctz(x) __builtin_ctzll(x)
#define csb(x) __builtin_popcountll(x)


#ifdef LOCAL
#include "debug.h"
#else
#define deb(...) (void)0
#endif

mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int dx4[4] = {0, 0, 1, -1}, dy4[4] = {1, -1, 0, 0};
const int mod = 1e9 + 7;
const int N = 200005; ///////////////////////////////////////
const ll inf = 1e15; /////////////////////////////////////////////

ll n, m, x, y, z, q, k, u, v, w;
vector<int> gr[N];
int sz[N];
int tot, done[N], cenpar[N];
void calc_sz(int node, int p) {
  tot ++;
  sz[node] = 1;
  for (auto ch : gr[node]) {
    if(ch == p || done[ch]) continue;
    calc_sz(ch, node);
    sz[node] += sz[ch];
  }
}
int find_cen(int node, int p) { // find centroid
  for (auto ch : gr[node]) {
    if(ch == p || done[ch]) continue;
    else if(sz[ch] > tot / 2) return find_cen(ch, node);
  }
  return node;
}
void decompose(int node, int p) { // find centroid of subtree of node, and assign p as parent of the centroid 
  tot = 0;
  calc_sz(node, 0);
  int cen = find_cen(node, 0);
  cenpar[cen] = p;
  done[cen] = 1;
  for(auto ch : gr[cen]) {
    if(ch == p || done[ch]) continue;
    decompose(ch, cen);
  }
}
vll cen_gr[N]; // centroid tree
int form_cen_gr() { // form graph, return root(centroid)
    decompose(1, 0);
    int root;
    L(i, 1, n) {
        if(cenpar[i] == 0) root = i;
        if(cenpar[i] != 0) {
            cen_gr[i].push_back(cenpar[i]);
            cen_gr[cenpar[i]].push_back(i);
        }
    }
    return root;
}

void prep(){
    
}

bool dead[N];
vector<ar<ll,2>> wgr[N];
vll best(1000006, inf);
ll ans;
vll tem;

void dfs2(ll node, ll par, ll len, ll cnt) { // on main graph ofc
    if(len <= 1000005) best[len] = min(best[len], cnt), tem.push_back(len);
    deb(node, len, cnt, best[len]);
    for(auto [ch, w] : wgr[node]) {
        if(ch==par || dead[ch]) continue;
        dfs2(ch, node, len+w, cnt+1);
    }
}

void dfs1(ll node, ll par, ll len, ll cnt) { // on main graph ofc
    if(k-len >= 0 and k-len <= 1000005 and best[k - len] != inf) ans = min(ans, best[k - len] + cnt), deb(best[k - len]);
    deb(node, len, cnt);
    for(auto [ch, w] : wgr[node]) {
        if(ch==par || dead[ch]) continue;
        dfs1(ch, node, len+w, cnt+1);
    }
}

void run(int peak) {
    dead[peak] = 1; 
    for(ll x : tem) best[x] = inf;
    tem.clear();

    deb(peak); deb(tem);
    for(auto [ch, w] : wgr[peak]) {
        if(ch ) {
            dfs1(ch, peak, w, 1);
            dfs2(ch, peak, w, 1);
        }
    } deb(peak, ans);

    for(auto ch : cen_gr[peak]) {
        if(ch and !dead[ch]) run(ch);
    }
}



int best_path(int N, int K, int H[][2], int L[]) {
    n = N; k = K;
    L(i, 1, n-1) {
        u = H[i-1][0]; v = H[i-1][1]; u++; v++; w = L[i-1];
        wgr[u].push_back({v, w}); wgr[v].push_back({u, w});
        gr[u].push_back(v); gr[v].push_back(u);
    }
    int cen = form_cen_gr();
    ans = inf;
    run(cen);
    return (ans==inf) ? -1 : ans;
}




// void solve(int tcase){
    
//     // testcases ?

//     // cleanup ?

//     cin >> n >> k;
//     int H[n-1][2]; int L[n-1];
//     L(i, 0, n-2) {
//         cin >> u >> v >> w; H[i][0] = u, H[i][1] = v, L[i] = w;
//     }
//     cout << best_path(n,k,H,L) << nl;
// }
// int main() {
//     ios_base::sync_with_stdio(false); cin.tie(NULL);
//     prep();
//     int tcase = 1;
//     // int t; cin >> t; for(; tcase <= t; ++tcase)
//     solve(tcase);
// }

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