Submission #1261800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261800		hickwhither	Race (IOI11_race)	C++20	100 / 100	386 ms	92928 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 <map>

using namespace std;

int numNode, desiredLength;
vector<int> e[int(2e5+3)];
vector<pair<int,int>> elen[int(2e5+3)];
int ans = 1e9+69;

int sz[int(2e5+3)], bigchild[int(2e5+3)];
int length[int(2e5+3)], depth[int(2e5+3)];

void size(int u=0, int p=-1){
    for(auto &[v,w] : elen[u])if(v!=p){
        length[v] = length[u] + w;
        depth[v] = depth[u] + 1;
        size(v, u);
        if(sz[v] > sz[bigchild[u]]) bigchild[u] = v;
    }
}

map<int,int> mp[int(2e5+3)];
void process(int u=0, int p=-1){
    // cout << u << ". " << length[u] << ' ' << depth[u] << '\n';
    
    mp[u][length[u]] = depth[u];
    
    for(int &v : e[u])if(v!=p){
        process(v, u);
        if(mp[u].size() < mp[v].size()) swap(mp[u], mp[v]);
        
        for(auto &x : mp[v])
        if(mp[u].find(2*length[u] + desiredLength - x.first) != mp[u].end()){
            ans = min(ans, mp[u][2*length[u] + desiredLength - x.first] + x.second - 2*depth[u]);
            // cout << length[u]  << ' ' << x.first << ' ' << 2*length[u] + desiredLength - x.first << " ~ ";
            // cout << x.second << ' ' << mp[u][2*length[u] + desiredLength - x.first] << endl;
        }

        for(auto &x : mp[v]){
            if(mp[u].find(x.first) != mp[u].end())
                mp[u][x.first] = min(mp[u][x.first], mp[v][x.first]);
            else mp[u][x.first] = mp[v][x.first];
        }
    }
    // cout << u << ". " << endl;
    // for(auto &x : mp[u]) cout << x.first << ' ' << x.second << endl;
}

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]);
    }

    for(int i=0; i<numNode; ++i) bigchild[i] = numNode;
    size();
    process();

    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: 22 / 22
• Subtask 4: 57 / 57