Submission #1122424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122424		fuwad	Race (IOI11_race)	C++14	0 / 100	4 ms	4948 KiB

race

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(v) (v).begin(), (v).end()

const ll oo = 1e17;
const int mod = 1e9+7; // 998244353;
const int maxn = 2e5;

vector<pair<ll, ll>> adj[maxn+1];
bool bad[maxn+1];
int subtree_size[maxn+1];
ll k, ans;

void dfs_ssz(int v, int p){
    subtree_size[v]=1;
    for(auto [c, w]: adj[v]){
        if(c^p and !bad[c]){
            dfs_ssz(c, v);
            subtree_size[v]+=subtree_size[c];
        }
    }
}

int find_centroid(int v, int p, int sz){
    for(auto [c, w]: adj[v]){
        if(!bad[c] and c^p and subtree_size[c]*2>sz)
            return find_centroid(c, v, sz);
    }
    return v;
}

void calc(int v, int p, ll depth, ll weight, map<ll,ll>& mp, bool update){
    if(update){
        if(mp.count(weight)){
            mp[weight] = min(mp[weight], depth);
        }
        else{
            mp[weight] = depth;
        }
    }
    else{
        ll temp = k-weight;
        if(mp.count(temp)){
            ans = min(ans, depth+mp[temp]+1);
        }
    }
    for(auto [c, w]: adj[v]){
        if(!bad[c] and c^p){
            calc(c, v, depth+1, weight+w, mp, update);
        }
    }
}

void decompose(int v, int p){
    dfs_ssz(v, p);
    int cen = find_centroid(v, p, subtree_size[v]);
    bad[cen]=1;
    map<ll, ll> mp;
    mp[0] = 0;
    for(auto [c, w]: adj[cen]){
        if(!bad[c]){
            calc(c, cen,1, w, mp,false);
            calc(c, cen,1, w, mp,true);
        }
    }
    for(auto [c, w]: adj[cen]){
        if(!bad[c]){
            decompose(c, cen);
        }
    }

}

int best_path(int N, int K, int H[][2], int L[]){
    k = K, ans = INT_MAX;
    for(int i = 0; i < N-1; i++){
        adj[H[i][0]+1].push_back({H[i][1]+1, L[i]});
        adj[H[i][1]+1].push_back({H[i][0]+1, L[i]});
    }
    decompose(1, 0);
    if(ans==INT_MAX)
        return -1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs_ssz(int, int)':
race.cpp:17:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |     for(auto [c, w]: adj[v]){
      |              ^
race.cpp: In function 'int find_centroid(int, int, int)':
race.cpp:26:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |     for(auto [c, w]: adj[v]){
      |              ^
race.cpp: In function 'void calc(int, int, ll, ll, std::map<long long int, long long int>&, bool)':
race.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |     for(auto [c, w]: adj[v]){
      |              ^
race.cpp: In function 'void decompose(int, int)':
race.cpp:61:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |     for(auto [c, w]: adj[cen]){
      |              ^
race.cpp:67:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |     for(auto [c, w]: adj[cen]){
      |              ^

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