제출 #1144062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144062		pedreitorzelda	경주 (Race) (IOI11_race)	C++20	9 / 100	168 ms	42912 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<bool>vis;
vector<map<ll,ll>>nodes;
vector<pair<ll,ll>>to_add; // lz propagation for subtrees
vector<vector<pair<ll,ll>>>g;
ll n,k;
ll cur_ans = -1;
void merge(ll node1, pair<ll,ll>b){
    ll node2 = b.first;
    ll val = b.second;

    // check good answer for current node
    pair<ll,ll>cur_node_check = make_pair(val,1);

    cur_node_check.first+=to_add[node2].first;
    cur_node_check.second+=to_add[node2].second;

    //cout << "SEARCHING " << cur_node_check.first << " " << cur_node_check.second << " " << to_add[node1].first << " " << to_add[node1].second << " " << to_add[node2].first << " " << to_add[node2].second<<" "<<endl; //<< change.first << " " << change.second<< endl;
    if(nodes[node2].find(k-cur_node_check.first)!=nodes[node2].end()){
        if(cur_ans==-1)cur_ans = cur_node_check.second+nodes[node2][k-cur_node_check.first];
        else cur_ans=min(cur_ans,cur_node_check.second+nodes[node2][k-cur_node_check.first]);
    }

    //pair<ll,ll>change = {0,0};
    if(nodes[node2].size()>nodes[node1].size()){
        swap(nodes[node1],nodes[node2]);
        swap(to_add[node1],to_add[node2]);
        to_add[node1].first+=val;
        to_add[node1].second++;

        //change.first+=val;
        //change.second++;
    }else{
        to_add[node2].first+=val;
        to_add[node2].second++;
    }
    // check good answers
    for(pair<ll,ll>it : nodes[node2]){
        it.first+=to_add[node2].first;
        it.second+=to_add[node2].second;

        it.first+=to_add[node1].first;
        it.second+=to_add[node1].second;

        //cout << "SEARCHING " << it.first << " " << it.second << " " << to_add[node1].first << " " << to_add[node1].second<< endl;
        if(nodes[node1].find(k-it.first)!=nodes[node1].end()){
            if(cur_ans==-1)cur_ans = it.second+nodes[node1][k-it.first];
            else cur_ans=min(cur_ans,it.second+nodes[node1][k-it.first]);
        }
    }

    // add current node

    pair<ll,ll>cur_node_val = make_pair(val-to_add[node2].first,1-to_add[node2].second);

    if(nodes[node2].find(cur_node_val.first)==nodes[node2].end())nodes[node2][cur_node_val.first]=cur_node_val.second;
    else nodes[node2][cur_node_val.first]=min(cur_node_val.second,nodes[node2][cur_node_val.first]);

    // remake nodes[node2]
    for(pair<ll,ll> it : nodes[node2]){
        it.first+=to_add[node2].first;
        it.second+=to_add[node2].second;

        it.first-=to_add[node1].first;
        it.second-=to_add[node1].second;
        
        // add to current node
        if(nodes[node1].find(it.first)==nodes[node1].end())nodes[node1][it.first]=it.second;
        else nodes[node1][it.first]=min(it.second,nodes[node1][it.first]);
    }
    // restore to_add
    to_add[node2]=make_pair(0,0);
}


void dfs(ll u){
    if(vis[u])return;
    vis[u]=true;
    for(auto it : g[u]){
        if(!vis[it.first]){
            dfs(it.first);
            merge(u,it);

            
            //cout << u << ":  ";
            //for(auto it2 : nodes[u]){
            //    cout << "("<<it2.first << ", " << it2.second << ")" << " ";
            //}cout << "--- " << to_add[u].first << ", " << to_add[u].second << endl;
        }
    }

    return;
}

int best_path(int N, int K,int H[][2], int L[]){
    if(K==1){
      return 0;
    }
    nodes.resize(N+2);
    vis.resize(N+2,0);
    to_add.resize(N+2,{0,0});
    g.resize(N+2);
    n=N,k=K;
    cur_ans = -1;
    for(ll i=0;i<N-1;i++){
        g[H[i][0]].push_back({H[i][1],L[i]});
        g[H[i][1]].push_back({H[i][0],L[i]});
    }ll root = 0;
    for(ll i=0;i<N;i++){
        if(g[root].size()>g[i].size())root=i;
    }dfs(root);// g[root].size()==1 siempre

    nodes.clear();
    vis.clear();
    g.clear();
    to_add.clear();
    return cur_ans;
}

/*
signed main(){
    ll t;
    cin >> t;
    while(t--){

        int n,k;
        cin >> n >> k;
        int H[n][2];
        int L[n];
        for(int i=0;i<n-1;i++){
            for(int j=0;j<2;j++){
                cin >> H[i][j];
            }
        }
        for(int i=0;i<n-1;i++)cin >> L[i];
        cout << best_path(n,k,H,L) << endl;
    }
    return 0;
}
*/

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