Submission #856721

#	Time	Username	Problem	Language	Result	Execution time	Memory
856721		alicanyaz	Race (IOI11_race)	C++14	0 / 100	3 ms	8792 KiB

race

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>
#define xc3(x) (x*(x-1)*(x-2)/6)
#define xc2(x) ((x)*((x)-1)/2)
#define abs(x) ((x)>0?(x):-((x)))
#define min(x,y) ((x)>(y)?(y):(x))
//#define debug 1
using namespace std;
using namespace __gnu_pbds;
//void FILEREAD(){freopen("text_input.txt","r",stdin);freopen("output.txt","w",stdout);}
#define ll long long
#define ull unsigned long long
#define pi pair<int,int>
#define pll pair<long long,long long>
#define pli pair<long long,int>
#define pil pair<int,long long>
#define vi vector<int>
#define vll vector<long long>
#define vpi vector<pair<int,int>>
#define vpll vector<pair<long long,long long>>
#define vvi vector<vector<int>>
#define vvll vector<vector<long long>>
#define vvpi vector<vector<pair<int,int>>>
#define vvpll vector<vector<pair<long,long>>>
#define vec vector
#define pr pair
#define fi first
#define se second
#define fr(i,j) for(int i=0;i<j;i++)
#define testcase(x) int x;cin>>x;while(x--)solve()
#define vecinp(v) for(auto &in_vx:v)cin>>in_vx
#define pb push_back
typedef tree<ll,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_Set;
ordered_Set os;
#define MAX 99999997
#define MOD 92182
#define maxM 200002
vvpi adj(maxM,vpi(0));
vec<bool> visited(maxM);
vi prec(maxM);
ll ans = LLONG_MAX;
int NN,KK;
void edge(int v1,int v2,int val){
        adj[v1].pb({v2,val});
        adj[v2].pb({v1,val});
}
int precf(int n,int p){
    prec[n] = 1;
    for(auto &x:adj[n]){
        if(x.first!=p && !visited[x.first])prec[n] += precf(x.first,n);
    }
    return prec[n];
}
int centroid(int n){
    int u = precf(n,-1);
    int p = n, l = -1;
    for(int i=0;i<adj[p].size();i++){
        int x = adj[p][i].first;
        if(x==l || visited[x])continue;
        if(prec[x]*2>u){
            i=-1;
            l=p;
            p=x;
        }
    }
    return p;
}
int d = 0;
vi cnt(maxM,MAX);
void dfs(int type, int node , int parent , int complexity , int km){
    if(km>KK)return;
    d = max(d,complexity);
    if(type) ans = min(ans,cnt[KK-km]+complexity);
    else cnt[km] = min(cnt[km],complexity);
    for(auto &x:adj[node]){
        if(x.first == parent || visited[x.first])continue;
        dfs(type,x.first,node,complexity+1,km+x.second);
    }
}

void solve(int n){
    int cen = centroid(n);
    visited[cen] = 1;
    cnt[0]=1;
    // MAIN OPERATIONS
    d = 0;
    for(auto &x:adj[cen]){
        if(visited[x.first])continue;
        dfs(1,x.first,cen,1,x.second);
        dfs(0,x.first,cen,1,x.second);
    }
    fill(cnt.begin(),cnt.begin()+d+5,MAX);
    // GO TO MY CHILDREN AND REPEAT
    for(auto &x:adj[cen]){
        if(visited[x.first])continue;
        solve(x.first);
    }

}
int best_path(int N,int K,int H[][2], int L[]){
    // OUTPUT && REMOVE LATER
    fr(i,N-1){
        edge(H[i][0],H[i][1],L[i]);
    }
    NN = N;
    KK = K;
    // MAIN CODE STARTS HERE
    //
    solve(0);
    return (ans>N?-1:ans);
}
/*int main(){
    int N,K; N = 11; K = 12;
    int H[N-1][2];
    for(int i=0;i<N-1;i++){
        cin >> H[i][0] >> H[i][1];
    }
    int L[N-1];
    for(int i=0;i<N-1;i++){
        cin>> L[i];
    }
    cout << best_path(N,K,H,L);
}*/

Compilation message (stderr)

race.cpp: In function 'int centroid(int)':
race.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i=0;i<adj[p].size();i++){
      |                 ~^~~~~~~~~~~~~~

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