제출 #1024824

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1024824		idas	경주 (Race) (IOI11_race)	C++11	100 / 100	1175 ms	54296 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
#define s second
#define f first

using namespace std;

typedef pair<int, int> pii;

const int MxN=2e5+10;
vector<pii> ad[MxN];
bool v[MxN];
int sz[MxN];

void get_sizes(int u, int pst=-1)
{
    sz[u]=1;
    for(auto it : ad[u]){
        int x=it.f;
        if(v[x] || x==pst) continue;
        get_sizes(x, u);
        sz[u]+=sz[x];
    }
}

int get_centroid(int u, int max_size, int pst=-1)
{
    for(auto it : ad[u]){
        int x=it.f;
        if(v[x] || x==pst) continue;
        if(sz[x]>max_size/2){
            return get_centroid(x, max_size, u);
        }
    }
    return u;
}

void trav(int u, multiset<pii> &st, int w_sum, int cn, int pst=-1)
{
    st.insert({w_sum,cn});
    for(auto it : ad[u]){
        int x=it.f, w=it.s;
        if(v[x] || x==pst) continue;
        trav(x, st, w_sum+w, cn+1, u);
    }
}

int ans=1e9;
void calc_paths(int u, int k)
{
    int nb=ad[u].size();
    multiset<pii> st[nb], full;
    FOR(i, 0, nb)
    {
        int x=ad[u][i].f, w=ad[u][i].s;
        if(v[x]) continue;
        trav(x, st[i], w, 1, u);
        for(auto it : st[i]){
            full.insert(it);
        }
    }

    full.insert({0,0});

//    cout << u << ":\n";
//    for(auto it : full){
//        cout << it.f << " " << it.s << '\n';
//    }

    FOR(i, 0, nb)
    {
        for(auto it : st[i]){
            full.erase(full.find(it));
        }

        for(auto it : st[i]){
            auto fnd=full.lower_bound({k-it.f,0});
            if(fnd!=full.end() && (*fnd).f==k-it.f){
                ans=min(ans, it.s+(*fnd).s);
            }
        }

        for(auto it : st[i]){
            full.insert(it);
        }
    }
}

void dfs(int u, int k)
{
    get_sizes(u);
    int ct=get_centroid(u, sz[u]);

//    cout << u << " " << ct << endl;

    calc_paths(ct, k);

    v[ct]=true;
    for(auto it : ad[ct]){
        int x=it.f;
        if(v[x]) continue;
        dfs(x, k);
    }
}

int best_path(int n, int k, int h[][2], int l[])
{
    FOR(i, 0, n-1)
    {
        ad[h[i][0]].pb({h[i][1],l[i]});
        ad[h[i][1]].pb({h[i][0],l[i]});
    }

    dfs(0, k);

    return (ans==int(1e9)?-1:ans);
}

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