제출 #900172

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
900172		subrat0018	경주 (Race) (IOI11_race)	C++17	21 / 100	3067 ms	57540 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define nline "\n"
using uint = unsigned int;
using ull = unsigned long long;
const ll M = 1e9 + 7;
const ll M2 = 998244353;
const ll INF = 2e18;
const ll N = 1e6 + 10;
const double Degree = 57.2958;

/***************************************Debug***********************************************************/
/***************************************Debug***********************************************************/
/***************************************Debug***********************************************************/


#ifndef ONLINE_JUDGE
#define debug(x) cerr<< #x << " ";_print(x);cerr<<nline;
#else
#define debug(x)
#endif
void _print(int x) {cerr << x;}
void _print(bool x) {cerr << x;}
void _print(char x) {cerr << x;}
void _print(string x) {cerr << x;}
void _print(ll x) {cerr << x;}
void _print(ull x) {cerr << x;}
void _print(float x) {cerr << x;}
void _print(double x) {cerr << x;}
template<class T>void _print(set<T> v);
template<class T>void _print(vector<T> v);
template<class T>void _print(multiset<T> v);
template<class T>void _print(unordered_set<T> v);
template<class T, class V>void _print(map<T, V> v);
template<class T, class V>void _print(unordered_map<T, V> v);
template<class T>void _print(vector<vector<T>> v);
template<class T>void _print(stack<T> v);
template<class T>void _print(queue<T> v);
template<class T, class V>void _print(pair<T, V> p);
template<class T>void _print(queue<T> v) {cerr << "[ "; while (!v.empty()) {_print(v.front()); cerr << " "; v.pop();} cerr << " ]";}
template<class T>void _print(stack<T> v) {cerr << "[ "; while (!v.empty()) {_print(v.top()); cerr << " "; v.pop();} cerr << " ]";}
template<class T, class V>void _print(pair<T, V> p) {_print(p.first); cerr << " "; _print(p.second); cerr << nline;}
template<class T>void _print(set<T> v) {cerr << "[ "; for (auto &i : v) {_print(i); cerr << " ";} cerr << "]";}
template<class T>void _print(vector<T> v) {cerr << "[ "; for (auto &i : v) {_print(i); cerr << " ";} cerr << "]";}
template<class T>void _print(multiset<T> v) {cerr << "[ "; for (auto &i : v) {_print(i); cerr << " ";} cerr << "]";}
template<class T>void _print(unordered_set<T> v) {cerr << "[ "; for (auto &i : v) {_print(i); cerr << " ";} cerr << "]";}
template<class T, class V>void _print(map<T, V> v) {cerr << "[ "; for (auto &i : v) {_print(i.first); cerr << " "; _print(i.second); cerr << "\n";} cerr << "]";}
template<class T, class V>void _print(unordered_map<T, V> v) {cerr << "[ "; for (auto &i : v) {_print(i.first); cerr << " "; _print(i.second); cerr << "\n";} cerr << "]";}
template<class T>void _print(vector<vector<T>> v) {cerr << "[ "; for (auto &i : v) {_print(i); cerr << nline;} cerr << "]";}



/************************************************************************************************************/
/************************************************************************************************************/
/************************************************************************************************************/

ll n,k;
ll sz[N];
bool dead[N];
ll dist[N];
vector<pair<ll, ll>> g[N];
vector<ll> temp;
void prep(int v,ll d, ll len, int par = -1)
{
    if(len > k)return;
    dist[len] = min(dist[len], d);
    temp.push_back(len);
    for(auto &val:g[v])
    {
        if(val.first == par || dead[val.first])continue;
        prep(val.first, d + 1, len + val.second, v);
    }
}

ll func(int v, ll d, ll len, int par = -1)
{
    if(len > k)return INF;
    ll ans = d + dist[k - len];
    debug(v);
    debug(d);
    debug(dist[k - len]);
    for(auto &val:g[v])
    {
        if(val.first == par || dead[val.first])continue;
        ans = min(ans, func(val.first, d + 1, len + val.second, v));
    }
    return ans;
}

void dfs(int v, int par=-1)
{
    sz[v] = 1;
    for(auto &val:g[v])
    {
        if(val.first != par && !dead[val.first])
        {
            dfs(val.first, v);
            sz[v] += sz[val.first];
        }
    }
}
int find_centroid(int currSize, int v, int par = -1)
{
    for(auto &val:g[v])
        if(val.first != par && !dead[val.first] && 2 * sz[val.first] > currSize)
            return find_centroid(currSize, val.first, v);
    return v;
}

ll decompose(int v)
{
    dfs(v);
    int centorid = find_centroid(sz[v], v);
    dead[centorid] = true;
    
    ll ans = INF;
    temp.clear();
    dist[0] = 0;
    for(auto &val:g[centorid])
    {
        if(!dead[val.first])
        {
            ans = min(func(val.first, 1, val.second, centorid), ans);
            prep(val.first, 1, val.second, centorid);
        }
    }
    dist[0] = INF;
    for(auto &val:temp)
        dist[val] = INF;
    for(auto &val:g[centorid])
        if(!dead[val.first])
            ans = min(ans, decompose(val.first));
    return ans;
}
int best_path(int nn, int K, int H[][2], int* L)
{
    n = nn;
    k = K;
    vector<pair<ll, ll>> arr;
    for(int i=0;i<N;i++)
        dist[i] = INF;
    for(int i=0;i<n-1;i++)
    {
        ll u,v;
        u = H[i][0];
        v = H[i][1];
        arr.push_back({u,v});
    }
    int ct = 0;
    for(auto &val:arr)
    {
        ll w;
        w = L[ct++];
        g[val.first].push_back({val.second, w});
        g[val.second].push_back({val.first, w});
    }
    ll ans = decompose(0);
    if(ans >= INF)
        return -1;
    else
        return ans;
}

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