제출 #245903

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
245903		ajpiano	Museum (CEOI17_museum)	C++14	20 / 100	19 ms	1152 KiB

museum

#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

#define FOR(a,b) for(int a=0;a<b;a++)
#define F0R(a,b,c) for(int a = b; a<=c; a++)
#define f first
#define s second
#define m0(x) memset(x,0,sizeof(x))
#define all(x) x.begin(), x.end()


typedef pair<int,int> pi;
typedef long long ll;
typedef vector<int> vi;
typedef vector<pi> vpi;

const int large = 1e4+1;

const int inf = 1e9;

int n,k,x;

vpi edges[large];

bool regcomp(const pi &a, const pi &b){
    if(a.f != b.f) return (a.f < b.f);
    else return (a.s > b.s);
}

bool greecomp(const pi &a, const pi &b){
    if(2*a.f-a.s != 2*b.f-b.s) return (2*a.f-a.s < 2*b.f-b.s);
    else return (a.f < b.f);
}


int dfs(int child, int parent, vpi &reg, vpi &greedy){
    int children = 1;
    int ptr = 0;
    vpi csize;
    vector<vpi> chilreg,chilgree;
    for(auto &a: edges[child]){
        if(a.f == parent) continue;
        chilreg.resize(ptr+1);
        chilgree.resize(ptr+1);
        int c = dfs(a.f,child,chilreg[ptr],chilgree[ptr]);
        for(auto &b: chilreg[ptr]){
            b.f += a.s;
            b.s += a.s;
        }
        for(auto &b: chilgree[ptr]){
            b.f += a.s;
            b.s += a.s;
        }
        children += c;
        csize.push_back({c,ptr});
        ptr++;
    }
    int nsz = min(children,k);
    reg.resize(nsz+1,{inf,0});
    greedy.resize(nsz+1,{inf,0});
    reg[1].f = 0;
    greedy[1].f = 0;
    sort(all(csize),greater<pi>());
    int chilcnt = 1;
    for(auto &a: csize){
        int c = a.f; ptr = a.s;
        int sz = min(c,k);
        for(int i = min(chilcnt,k-1); i >= 1; i--){
            F0R(j,1,sz){
                if(i+j> nsz) break;
                //reg
                pi b = {reg[i].f+chilreg[ptr][j].f,max(reg[i].s,chilreg[ptr][j].s)};
                reg[i+j]= min(reg[i+j],b,regcomp);
                //greedy
                greedy[i+j] = min(greedy[i+j],b,greecomp);
                b = {greedy[i].f+chilreg[ptr][j].f,max(greedy[i].s,chilreg[ptr][j].s)};
                greedy[i+j] = min(greedy[i+j],b,greecomp);
                b = {reg[i].f+chilgree[ptr][j].f,max(reg[i].s,chilgree[ptr][j].s)};
            }
        }
        chilcnt += c;
    }
    return children;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k >> x;
    FOR(i,n-1){
        int a,b,c; cin >> a >> b >> c;
        edges[a].push_back({b,c});
        edges[b].push_back({a,c});
    }
    vpi reg,greedy;
    dfs(x,0,reg,greedy);
    cout << 2*greedy[k].f-greedy[k].s << "\n";
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 25
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20