제출 #762410

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
762410		JakobZorz	Race (IOI11_race)	C++14	100 / 100	1022 ms	79496 KiB

race

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

using namespace std;
typedef long long ll;

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

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'll get_pairs2(std::vector<std::pair<long long int, long long int> >&, std::vector<std::pair<long long int, long long int> >&, ll)':
race.cpp:74:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         while(l<b.size()&&b[l].first<rec)
      |               ~^~~~~~~~~
race.cpp:76:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         if(l<b.size()&&b[l].first+i.first==s)
      |            ~^~~~~~~~~

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