Submission #761944

#	Time	Username	Problem	Language	Result	Execution time	Memory
761944		JakobZorz	경주 (Race) (IOI11_race)	C++14	21 / 100	33 ms	18332 KiB

race

#include "race.h"
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#include <iostream>

using namespace std;
typedef long long ll;

int k;
set<pair<int,int>> nodes[50000];
int parents[50000];
int sub_size[50000];
int depth[50000];
int abs_depth[50000];
 
void init_tree(int node,int par,int d=0,int abs_d=1){
    //cout<<node+1<<" "<<par+1<<"\n";
    parents[node]=par;
    depth[node]=d;
    abs_depth[node]=abs_d;
    sub_size[node]=0;
    for(pair<int,int> ne:nodes[node]){
        if(ne.first!=par){
            init_tree(ne.first,node,d+ne.second,abs_d+1);
            sub_size[node]+=sub_size[ne.first];
        }
    }
    sub_size[node]++;
    //cout<<"done "<<node+1<<"\n";
}
 
int get_centroid(int node){
    int n=sub_size[node];
    int centroid=node;
    while(sub_size[centroid]>n/2){
        int biggest_size=-1;
        int biggest=-1;
        for(pair<int,int> ne:nodes[centroid]){
            //cout<<ne<<" "<<parents[centroid]<<" "<<sub_size[ne]<<"\n";
            if(ne.first!=parents[centroid]&&sub_size[ne.first]>=biggest_size){
                biggest_size=sub_size[ne.first];
                biggest=ne.first;
            }
        }
        centroid=biggest;
    }
    return parents[centroid];
}
 
vector<pair<int,int>> get_depths(int node, int add){
    vector<pair<int,int>> depths;
    queue<int> q;
    q.push(node);
    while(!q.empty()){
        int c=q.front();
        q.pop();
        depths.push_back({depth[c]+add,abs_depth[c]});
        for(pair<int,int> ne:nodes[c])
            if(ne.first!=parents[c])
                q.push(ne.first);
    }
    
    return depths;
}
 
int get_pairs2(vector<pair<int,int>>&a,vector<pair<int,int>>&b,int s){
    reverse(a.begin(),a.end());
    int l=0;
    int res=1000000;
    for(pair<int,int> i:a){
        int rec=s-i.first;
        while(l<(int)b.size()&&b[l].first<rec)
            l++;
        if(l<(int)b.size()&&b[l].first+i.first==s)
            res=min(res,b[l].second+i.second);
    }
    //cout<<"pairs2: "<<res<<"\n";
    return res;
}
 
int get_pairs(vector<vector<pair<int,int>>>vec,int s){
    /*cout<<"-------\n";
    for(vector<int> i:vec){
        for(int j:i)
            cout<<j<<" ";
        cout<<"\n";
    }*/
    
    int n=(int)vec.size();
    if(n==1){
        auto iter=lower_bound(vec[0].begin(),vec[0].end(),pair<int,int>(s,0));
        if(iter==vec[0].end()||iter->first!=s)
            return 1000000;
        return iter->second;
    }
    int res=1000000;
    int m=n/2;
    vector<pair<int,int>>a,b;
    for(int i=0;i<n;i++){
        if(i<m)
            a.insert(a.end(),vec[i].begin(),vec[i].end());
        else
            b.insert(b.end(),vec[i].begin(),vec[i].end());
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    res=min(res,get_pairs2(a,b,s));
    res=min(res,get_pairs({vec.begin(),vec.begin()+m},s));
    res=min(res,get_pairs({vec.begin()+m,vec.end()},s));
    //cout<<"pairs1: "<<res<<"\n";
    return res;
}
 
int get(int node){
    if(nodes[node].empty())
        return 1000000;
    
    int centroid=get_centroid(node);
    init_tree(centroid,centroid);
    vector<pair<int,int>> children(nodes[centroid].begin(),nodes[centroid].end());
    vector<vector<pair<int,int>>>vec;
    for(pair<int,int> child:children){
        nodes[centroid].erase(child);
        nodes[child.first].erase({centroid,child.second});
        init_tree(child.first,child.first);
        vec.push_back(get_depths(child.first,child.second));
    }
    
    int res=get_pairs(vec,k);
    for(pair<int,int> child:children){
        init_tree(child.first,child.first);
        res=min(res,get(child.first));
    }
    return res;
}

int best_path(int N, int K, int H[][2], int L[]) {
    int n=N;
    k=K;
    for(int i=0;i<n-1;i++){
        int a=H[i][0],b=H[i][1];
        nodes[a].insert({b,L[i]});
        nodes[b].insert({a,L[i]});
    }
    init_tree(0,0);
    int res=get(0);
    if(res>=1000000)
        return -1;
    return res;
}

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