Submission #441220

#	Time	Username	Problem	Language	Result	Execution time	Memory
441220		julian33	Race (IOI11_race)	C++14	0 / 100	3078 ms	4940 KiB

race

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cerr<<vars<<" = ";
    string delim="";
    (...,(cerr<<delim<<values,delim=", "));
    cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif

#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);}

const int mxN=2e5+5;

vector<pii> graph[mxN];
int seen[mxN],sub[mxN],ans=1e9,K;
unordered_map<int,int> mp;

void dfs(int at,int p){
    sub[at]=1;
    for(auto &[i,w]:graph[at]){
        if(i==p || seen[i])
            continue;
        dfs(i,at);
        sub[at]+=sub[i];
    }
}

int centroid(int at,int p,int s){
    for(auto &[i,w]:graph[at]){
        if(i==p || seen[i])
            continue;
        if(sub[i]>s/2)
            return centroid(i,at,s);
    }
    return at;
}

void solve(int at,int p,int len,int filling,int h){
    if(len>K)
        return;
    if(filling){
        if(mp.count(len))
            mina(mp[len],h);
        else
            mp[len]=h;
    } else{
        if(mp.count(K-len)){
            mina(ans,mp[K-len]+h);
        }
    }
    for(auto &[i,w]:graph[at]){
        if(i==p || seen[i])
            continue;
        solve(i,at,len+w,filling,h+1);
    }
}

void build(int at){
    dfs(at,-1);
    int s=sub[at];
    int cent=centroid(at,-1,s);
    mp.clear();
    for(auto &[i,w]:graph[cent]){
        solve(i,cent,w,0,1);
        solve(i,cent,w,1,1);
    }
    seen[cent]=1;
    for(auto &[i,w]:graph[cent]){
        if(seen[i])
            continue;
        build(i);
    }
}

int best_path(int n,int k,int h[][2],int l[]){
    K=k;
    for(int i=0;i<n-1;i++){
        graph[h[0][i]].pb({h[1][i],l[i]});
        graph[h[1][i]].pb({h[0][i],l[i]});
    }
    build(0);
    return (ans==1e9?-1:ans);
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:36:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |     for(auto &[i,w]:graph[at]){
      |               ^
race.cpp: In function 'int centroid(int, int, int)':
race.cpp:45:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |     for(auto &[i,w]:graph[at]){
      |               ^
race.cpp: In function 'void solve(int, int, int, int, int)':
race.cpp:67:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |     for(auto &[i,w]:graph[at]){
      |               ^
race.cpp: In function 'void build(int)':
race.cpp:79:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |     for(auto &[i,w]:graph[cent]){
      |               ^
race.cpp:84:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |     for(auto &[i,w]:graph[cent]){
      |               ^

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