Submission #969671

#	Time	Username	Problem	Language	Result	Execution time	Memory
969671		ReLice	Race (IOI11_race)	C++17	43 / 100	1532 ms	262144 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define ll int
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
//#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>*/
template<class S,class T>
bool chmin(S &a,const T &b) {
	return a>b?(a=b)==b:false;
}
template<class S,class T>
bool chmax(S &a,const T &b) {
	return a<b?(a=b)==b:false;
}
const ll inf=1e9+7;
const ll M=2e5+7;
vector<pll> g(M);
ll n,k;
vector<vll> cen(M);
ll sz[M];
pll dp[M];
ll ans=inf;
bool f[M];
void dfs_sz(ll v,ll p){
    sz[v]=1;
    for(auto i : g[v]){
        if(i.fr==p || f[i.fr]) continue;
        dfs_sz(i.fr,v);
        sz[v]+=sz[i.fr];
    }
}
ll find_cen(ll v,ll p,ll x){
    for(auto i : g[v]){
        if(i.fr==p || f[i.fr]) continue;
        if(sz[i.fr]>x/2)return find_cen(i.fr,v,x);
    }
    return v;
}
void calc(ll v,ll p){
    pll x;
    dp[v]={{0,0}};
    for(auto y : g[v]){
        ll i=y.fr,len=y.sc;
        if(i==p || f[i])continue;
        calc(i,v);
        ll l=0,r=0;
        for(ll j=0;j<dp[i].size();j++){
            dp[i][j].fr+=len;
            dp[i][j].sc++;
        }
        for(auto j : dp[i]){
            ll low=lb(all(dp[v]),make_pair(k-j.fr,0))-dp[v].begin();
            if(low<dp[v].size() && dp[v][low].fr==k-j.fr)chmin(ans,dp[v][low].sc+j.sc);
        }
        while(l<dp[i].size() || r<dp[v].size()){
            if(l<dp[i].size() && r<dp[v].size()){
                if(dp[i][l].fr==dp[v][r].fr){
                    x.pb({dp[i][l].fr,min(dp[i][l].sc,dp[v][r].sc)});
                    l++;
                    r++;
                }else if(dp[i][l].fr<dp[v][r].fr){
                    x.pb(dp[i][l]);
                    l++;
                }else {
                    x.pb(dp[v][r]);
                    r++;
                }
            }else if(l<dp[i].size()){
                x.pb(dp[i][l]);
                l++;
            }else{
                x.pb(dp[v][r]);
                r++;
            }
        }
        dp[v]=x;
        x.clear();
        while(dp[v].size() && dp[v].bc.fr>k)dp[v].pob;
    }
}
void cen_dec(ll v,ll p){
    dfs_sz(v,p);
    ll c=find_cen(v,p,sz[v]);
    f[c]=1;
    calc(c,0);
    for(auto i : g[c]){
        if(f[i.fr]) continue;
        cen_dec(i.fr,c);
    }
}
int best_path(int N, int K, int h[][2], int l[]){
    n=N,k=K;
    ll i,j,a,b;
    for(i=0;i<n-1;i++){
        a=h[i][0],b=h[i][1];
        a++;
        b++;
        g[a].pb({b,l[i]});
        g[b].pb({a,l[i]});
    }
    cen_dec(1,0);
    if(ans==inf)return -1;
    return ans;
}
/*
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
2
*/

Compilation message (stderr)

race.cpp: In function 'void calc(int, int)':
race.cpp:68:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for(ll j=0;j<dp[i].size();j++){
      |                    ~^~~~~~~~~~~~~
race.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             if(low<dp[v].size() && dp[v][low].fr==k-j.fr)chmin(ans,dp[v][low].sc+j.sc);
      |                ~~~^~~~~~~~~~~~~
race.cpp:76:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         while(l<dp[i].size() || r<dp[v].size()){
      |               ~^~~~~~~~~~~~~
race.cpp:76:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         while(l<dp[i].size() || r<dp[v].size()){
      |                                 ~^~~~~~~~~~~~~
race.cpp:77:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |             if(l<dp[i].size() && r<dp[v].size()){
      |                ~^~~~~~~~~~~~~
race.cpp:77:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |             if(l<dp[i].size() && r<dp[v].size()){
      |                                  ~^~~~~~~~~~~~~
race.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             }else if(l<dp[i].size()){
      |                      ~^~~~~~~~~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:114:10: warning: unused variable 'j' [-Wunused-variable]
  114 |     ll i,j,a,b;
      |          ^

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