Submission #1261036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261036		hickwhither	Race (IOI11_race)	C++20	21 / 100	3092 ms	22084 KiB

race

#define mocua(inp, out) if(fopen(inp,"r")){freopen(inp,"r",stdin);freopen(out,"w",stdout);}

#include <iostream>
#include <cstdint>
#include <climits>

#include <vector>
#include <cstring>

using namespace std;

int numNode, desiredLength;
vector<int> e[int(2e5+3)];
vector<pair<int,int>> elen[int(2e5+3)];

bool removed[int(2e5+3)];
int sz[int(2e5+3)];

int resize(int u, int p=-1){
    sz[u] = 1;
    for(int &v : e[u])
    if(!removed[v] && v!=p)
        sz[u] += resize(v, u);
    return sz[u];
}

int find_centroid(int targetsize, int u, int p=-1){
    for(int &v : e[u])
    if(!removed[v] && v!=p){
        if(sz[v] > targetsize) return find_centroid(targetsize, v, u);
    }
    return u;
}

const int LIM = 1e6;
int mp[LIM+3]; 

int ans = 1e9+69;
void progress(bool isUpd, int current_length, int depth, int u, int p=-1){
    if(current_length > desiredLength) return;
    if(isUpd) mp[current_length] = min(mp[current_length], depth);
    else{
        int f = desiredLength - current_length;
        if(f>=0)
            ans = min(ans, mp[f]+depth);
    }

    for(auto &[v,w] : elen[u])
    if(!removed[v] && v!=p){
        progress(isUpd, current_length+w, depth+1, v, u);
    }
}

void centroid_decomp(int u=0){
    u = find_centroid(resize(u)>>1, u);
    removed[u] = 1;

    // cout << "CENTROID " << u << '\n';
    memset(mp, 0x3f, sizeof mp);
    mp[0] = 0;
    
    for(auto &[v,w] : elen[u])
    if(!removed[v]){
        progress(0, w, 1, v);
        progress(1, w, 1, v);
    }

    for(int &v : e[u])
    if(!removed[v])
        centroid_decomp(v);
}

int best_path(int _numNode, int _desiredLength, int edge[][2], int edgeLength[]){
    numNode = _numNode;
    desiredLength = _desiredLength;
    for(int i=0; i<numNode; ++i)
        e[i].clear(),
        elen[i].clear();

    for(int i=0; i<numNode-1; ++i){
        e[edge[i][0]].emplace_back(edge[i][1]);
        e[edge[i][1]].emplace_back(edge[i][0]);
        elen[edge[i][0]].emplace_back(edge[i][1], edgeLength[i]);
        elen[edge[i][1]].emplace_back(edge[i][0], edgeLength[i]);
    }

    centroid_decomp();

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

// int edge[int(2e5+3)][2];
// int edgeLength[int(2e5+3)];

// signed main()
// {
//     cin.tie(0) -> sync_with_stdio(0);
    
//     int n, k;
//     cin >> n >> k;
//     for(int i=0, u, v; i<n-1; ++i) cin >> edge[i][0] >> edge[i][1];
//     for(int i=0; i<n-1; ++i) cin >> edgeLength[i];

//     cout << best_path(n, k, edge, edgeLength);

//     return 0;
// }

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