제출 #1318219

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318219		AzeTurk810	경주 (Race) (IOI11_race)	C++20	0 / 100	1 ms	332 KiB

race

/*
  _      __        __         __        ____                    ___    _                   __
 | | /| / / ___ _ / /_ ____  / /       / __ \  ___  ___        / _ \  (_) ___  ____ ___   / /
 | |/ |/ / / _ `// __// __/ / _ \     / /_/ / / _ \/ -_)      / ___/ / / / -_)/ __// -_) /_/ 
 |__/|__/  \_,_/ \__/ \__/ /_//_/     \____/ /_//_/\__/      /_/    /_/  \__/ \__/ \__/ (_)  
                                                                                             
*/

#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
// #pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
 
// constants

// functions
int GCD(int A, int B);
int LCM(int A, int B);
int power(int base, int exponent);

// structs
struct graph
{
    vector <vector <pair <int, int> > > g;
    vector <int> sz, mne;
    vector <bool> dead;
    int mncnt;
    
    void cleanse()
    {
        fill(dead.begin(), dead.end(), false);
        fill(mne.begin(), mne.end(), INT_MAX);
        mncnt = INT_MAX;
        mne[0] = 0;
    }
    
    void prep(int n, int k)
    {
        g.resize(n);
        sz.resize(n);
        dead.resize(n);
        mne.resize(k);
        
        cleanse();
    }
    
    void adde(int u, int v, int w)
    {
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    
    void DFS(int v, int P)
    {
        sz[v] = 1;
        for (auto [u, w] : g[v])
        {
            if (dead[u] || u == P)
            {
                continue;
            }
            
            DFS(u, v);
            sz[v] += sz[u];
        }
    }
    
    int getC(int v, int P, int mx)
    {
        for (auto [u, w] : g[v])
        {
            if (u == P || dead[u] || sz[u] <= mx)
            {
                continue;
            }
            return getC(u, v, mx);
        }
        return v;
    }
    
    void getD(int v, int P, int D, int lvl, bool B, vector <int> &changed, int &limit)
    {
        if (D > limit)
        {
            return;
        }
        
        if (B)
        {
            if (mne[limit - D] != INT_MAX)
            {
                mncnt = min(mncnt, lvl + mne[limit - D]);
            }
        }
        else
        {
            mne[D] = min(mne[D], lvl);
            changed.push_back(D);
        }
        
        for (auto [u, w] : g[v])
        {
            if (u == P || dead[u])
            {
                continue;
            }
            getD(u, v, D + w, lvl + 1, B, changed, limit);
        }   
    }
    
    void decomp(int v, int &limit)
    {
        DFS(v, -1);
        int c = getC(v, -1, sz[v] / 2);
        dead[c] = true;
        
        vector <int> changed;
        for (auto [u, w] : g[c])
        {
            if (dead[u])
            {
                continue;
            }
            
            getD(u, c, w, 1, true, changed, limit);
            getD(u, c, w, 1, false, changed, limit);
        }
        
        for (auto x : changed)
        {
            mne[x] = INT_MAX;
        }
        
        for (auto [u, w] : g[c])
        {
            if (dead[u])
            {
                continue;
            }
            
            decomp(u, limit);
        }
    }
};

// globals

// variables
int n, K;

// iterators
int i;

// notes
/*
My favorite anime is One Piece(obviously)
My oshi(Yes, I have an oshi, deal with it) is Kamil_Tsubaki

 -stuff you should look for-
* int overflow, array bounds
* special cases (n=1?)
* do something instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH

continue - skip the rest in the loop
*/
 

int best_path(int N, int K, int H[][2], int L[]) {
    graph G;
    G.prep(N, K);
    // return 0;
    for (int i = 0; i < N - 1; i++) {
        const int &u = H[i][0], &v = H[i][1], &w = L[i];
        G.adde(u, v, w);
    }
    G.decomp(1, K);
    return (G.mncnt == INT_MAX ? -1 : G.mncnt);
}

 
int GCD(int A, int B)
{
    if (!A)
    {
        return B;
    }
    return GCD(B % A, A);
}

int LCM(int A, int B)
{
    return A * B / GCD(A, B);
}

int power(int base, int exponent)
{
    int res = 1;
    while (exponent) 
    {
        if (exponent & 1)
        { 
            res *= base;
        }
        base *= base;
        exponent >>= 1;    
    }
    return res;
}

/*
$$$$$$$$\ $$$$$$$$\ 
$$  _____|\____$$  |
$$ |          $$  / 
$$$$$\       $$  /  
$$  __|     $$  /   
$$ |       $$  /    
$$$$$$$$\ $$$$$$$$\ 
\________|\________|
*/

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