Submission #1269285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269285		leanderson	경주 (Race) (IOI11_race)	C++20	0 / 100	5 ms	10560 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const ll MAXN = 2e5+50;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define optimize ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define endl "\n"
#define yes() cout << "YES\n"
#define no() cout << "NO\n"
//------------------solution starts below------------------//

vector<set<pair<int,int>>> g_adj(MAXN);
vector <int> sub(MAXN);
vector <bool> removed(MAXN);

int n,k;
int answer = INF;

int dfs_size(int u, int p){
    sub[u] = 1;
    for (auto &pr : g_adj[u]){
        int v = pr.first;
        if (v == p || removed[v]) continue;
        sub[u] += dfs_size(v, u);
    }
    return sub[u];
}
int dfs_find_centroid(int u, int p, int n){
    for (auto &pr : g_adj[u]){
        int v = pr.first;
        if (v == p || removed[v]) continue;
        if (sub[v] > n/2) return dfs_find_centroid(v, u, n);
    }
    return u;
}
void collect_paths(int u, int p, ll sum, int len, vector<pair<ll,int>> &out){
    if (sum > k) return;         
    out.emplace_back(sum, len); // armazena (soma, comprimento)
    for (auto &pr : g_adj[u]){
        int v = pr.first;
        int w = pr.second;
        if (v == p || removed[v]) continue;
        collect_paths(v, u, sum + w, len + 1, out);
    }
}
void process_centroid(int centroid){
    unordered_map<ll,int> best;
    best.reserve(32);
    best[0] = 0; 

    for (auto &pr : g_adj[centroid]){
        int v = pr.first;
        int w = pr.second;
        if (removed[v]) continue;

        vector<pair<ll,int>> paths;
        collect_paths(v, centroid, w, 1, paths);

        for (auto &pa : paths){
            ll s = pa.first;
            int len = pa.second;
            if (best.find(k - s) != best.end()){
                answer = min(answer, len + best[k - s]);
            }
        }

        for (auto &pa : paths){
            ll s = pa.first;
            int len = pa.second;
            auto it = best.find(s);
            if (it == best.end() || len < it->second) best[s] = len;
        }
    }
}
void decompose(int start){
    int n = dfs_size(start, -1);
    int centroid = dfs_find_centroid(start, -1, n);
    process_centroid(centroid);
    removed[centroid] = true;
    for (auto &pr : g_adj[centroid]){
        int v = pr.first;
        if (!removed[v]) decompose(v);
    }
}

void organize_edges(vector<pair<int,int>> &edges, vector<int> &weights){
    for (int i=0;i<n-1;i++){
        int u = edges[i].first;
        int v = edges[i].second;
        int w = weights[i];
        g_adj[u].insert({v,w});
        g_adj[v].insert({u,w});
    }
    decompose(0);
    if (answer == INF) cout << -1 << endl;
    else cout << answer << endl;
}
int best_path(int N, int K, int H[][2], int L[]) {
    n = N;
    k = K;
    vector<pair<int,int>> edges(n);
    vector<int> weights(n);

    for (int i=0;i<n-1;i++){
        int u = H[i][0];
        int v = H[i][1];
        edges[i] = {u,v};
    }
    for (int i=0;i<n-1;i++){
        int w = L[i];
        weights[i] = w;
    }
    organize_edges(edges,weights);
    if (answer == INF) return -1;
    return answer;
}
/*int main (){
    
    
    optimize;

    ll t;
    t = 1;
    //cin >> t;
    while(t--){
        solve();
    }    
    return 0;

}
*/

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