Submission #849643

#	Time	Username	Problem	Language	Result	Execution time	Memory
849643		not_from_here	Race (IOI11_race)	C++14	100 / 100	350 ms	68020 KiB

race

// ඞ
#pragma GCC optimize("Ofast")
//#pragma GCC target("popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#ifdef LOCAL
#include "debug.h"
#define dbg(...) debug_out(splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define dbg(...)
#endif

//#define int long long
#define itn int
#define ALL(v) (v).begin(), (v).end()
#define mem(a, x) memset(a , x , sizeof(a))
#define f first
#define s second
#define mb make_pair
#define pb push_back
#define popCnt __builtin_popcountll

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vector<int>> vvi;
typedef pair <int, int> pii;
typedef vector<pair <int, int>> vpii;
typedef vector<vector<char>> vvc;

const int mod = 1e9 + 7;
const int oo = 0x5f5f5f5f;
const long double PI = acos(-1.0L);

int ceiledLog2 (int x){return __lg(x) + (__builtin_popcount(x) != 1);}
ll toLL (int first, int second, int mx){return (1LL*first*mx) + second;}

template <class T, class U> T GCD (T a, U b) {return (!b ? a : GCD(b, a%b));}
template <class T, class U> T LCM (T a, U b) {return ((a/GCD(a, b)) * b);}
template <class T> bool isSquare (T n) {T sq = sqrt(n);  return (sq*sq)==n;}
template <typename T> T Unique(T x){sort(ALL(x));x.resize(distance(x.begin(),unique(ALL(x))));return x;}
template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//bool sortBySecond (pii &a, pii &b) {return a.second < b.second;} //asc

int ys[] = {-1, -1, 0, 1, 1, 1, 0, -1};     //edges [0, 2, 4, 6]
int xs[] = {0, 1, 1, 1, 0, -1, -1, -1};

//-----------------------------------------------------------------------------//

//const int N = ?e5 + 5;
int n,k;
vector<vpii> g;

int ans=2e9;
struct B_CH_SACK {
        int n, timer = 0;
        vector<int> lev,sz, b_ch;
        vector<ll>to;
        vector<int> order, tin, tout;
        map<ll, int> f;

        B_CH_SACK(int _n = 0) {
                n = _n;
                if (n) {
                        sz.resize(n, 1);
                        to.resize(n);
                        lev.resize(n);
                        b_ch.resize(n, -1);
                        tin.resize(n);
                        tout.resize(n);
                        dfs(0, -1);
                        solve(0, -1, false);
                }
        }

        void dfs(int u, int p, ll t=0, int d=0) {
                tin[u] = timer++;
                order.push_back(u);
                to[u]=t;
                lev[u]=d;
                int mx = 0, idx = -1;
                for (auto &[v,c] : g[u]) {
                        if (v == p) continue;
                        dfs(v, u, t+c,d+1);
                        sz[u] += sz[v];
                        if (sz[v] > mx) {
                                mx = sz[v];
                                idx = v;
                        }
                }
                b_ch[u] = idx;
                tout[u] = timer-1;
        }


        void solve(int u, int p, bool keep) {
                for (auto &[v,c] : g[u]) {
                        if (v == p || v == b_ch[u]) continue;
                        solve(v, u, false);
                }
                if (b_ch[u] != -1) {
                        solve(b_ch[u], u, true);
                }


                f[to[u]]=lev[u];
                for (auto &[v,c] : g[u]) {
                        if (v == p || v == b_ch[u]) continue;
                        for (int i = tin[v]; i <= tout[v]; i++) {
                                int x = order[i];
                                ll d=to[x]-to[u];
                                if (d>k) continue;
                                ll dif=k-d;
                                dif+=to[u];
                                if (f.count(dif)){
                                        ans=min(ans, f[dif]-lev[u] + lev[x]-lev[u]);
                                }
                        }
                        for (int i = tin[v]; i <= tout[v]; i++) {
                                int x = order[i];
                                if (f.count(to[x]))
                                        f[to[x]]=min(f[to[x]],lev[x]);
                                else
                                        f[to[x]]=lev[x];
                        }
                }

                ll need=to[u]+k;
                if (f.count(need)){
                        ans=min(ans, f[need]-lev[u]);
                }

                if (!keep) {
                        f.clear();
                }
        }
} sack;

int best_path(int N, int K, int h[][2], int l[]){
        n=N;
        k=K;
        g=vector<vpii>(n);
        for (int i = 0; i < n-1; ++i) {
                g[h[i][0]].pb({h[i][1], l[i]});
                g[h[i][1]].pb({h[i][0], l[i]});
        }
        sack=B_CH_SACK(n);
        if (ans > 1e8)
                return -1;
        return ans;
}

Compilation message (stderr)

race.cpp: In member function 'void B_CH_SACK::dfs(int, int, ll, int)':
race.cpp:91:28: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   91 |                 for (auto &[v,c] : g[u]) {
      |                            ^
race.cpp: In member function 'void B_CH_SACK::solve(int, int, bool)':
race.cpp:106:28: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  106 |                 for (auto &[v,c] : g[u]) {
      |                            ^
race.cpp:116:28: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  116 |                 for (auto &[v,c] : g[u]) {
      |                            ^

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