Submission #1143836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143836		pedreitorzelda	Race (IOI11_race)	C++20	0 / 100	0 ms	320 KiB

race

#include <bits/stdc++.h>
using namespace std;
vector<bool>vis;
vector<map<int,int>>nodes;
vector<pair<int,int>>to_add; // lz propagation for subtrees
vector<vector<pair<int,int>>>g;
int n,k;
int cur_ans = -1;
void merge(int node1, pair<int,int>b){
    int node2 = b.first;
    int val = b.second;
    swap(node1,node2);
    pair<int,int>change = {0,0};
    if(nodes[node1].size()>nodes[node2].size()){
        swap(nodes[node1],nodes[node2]);
        swap(to_add[node1],to_add[node2]);
        to_add[node2].first+=val;
        to_add[node2].second++;

        change.first+=val;
        change.second++;
    }else{
        to_add[node1].first+=val;
        to_add[node1].second++;
    }
    // add current node to to_add[node1]

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

    // check good answer for current node
    pair<int,int>cur_node_check = cur_node_val;

    cur_node_check.first+=change.first;
    cur_node_check.second+=change.second;

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

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

    // check good answers
    for(pair<int,int>it : nodes[node1]){
        it.first+=to_add[node1].first;
        it.second+=to_add[node1].second;

        it.first-=to_add[node2].first;
        it.second-=to_add[node2].second;

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

    // add current node
    if(nodes[node1].find(cur_node_val.first)==nodes[node1].end())nodes[node1][cur_node_val.first]=cur_node_val.second;
    else nodes[node1][cur_node_val.first]=min(cur_node_val.second,nodes[node1][cur_node_val.first]);

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

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


void dfs(int 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[]){
    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(int 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]});
    }int root = 0;
    for(int 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();
    return cur_ans;
}

/*
int main(){
    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: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57