Submission #1166537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166537		jcoves	Race (IOI11_race)	C++20	0 / 100	0 ms	320 KiB

race

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_RUN
    #include "debug_common.h"
    #else
    #define trace(...) ;
    #define dbg(...) ;
    #define dbgc(...) ;
    #define debug(x) ;
    #define debuga(a, n) ;
    #define debug2(x, y) ;
    #define debug3(x, y, z) ;
    #define debug4(x, y, z, w) ;
    #define debug5(a,b,c,d,e) ;
    #define lassert(x) ;
    #define dassert(x, ...) ;
    int recur_depth = 0; bool rec_indent = true;
    const bool isLocal = false;
    #endif

    #define pb push_back
    #define eb emplace_back
    #define popb pop_back
    #define all(v) begin(v), end(v)
    #define rall(v) (v).rbegin(),(v).rend()
    #define make_unique(v) (v).erase(unique(all(v)), (v).end())
    #define sz(c) ((int) c.size())
    #define forn(i,n) for(auto i=(n)-(n);i<(n);i++)
    #define fornn(i,s,n) for(auto i=(n)-(n)+(s);i<(n);i++)
    #define forb(i,n) for(auto i=(n)-1;i>=0;i--)
    #define forbn(i,s,n) for(auto i=(n)-1;i>=(s);i--)
    #define forbit(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
    #define mem(a,b) memset(a,b,sizeof(a))
    #define abs(x) (((x) < 0) ? -(x) : (x))
    #define sqr(x) ((x) * (x))
    #define sqrt(x) sqrt(abs(x))
    #define has(c,x) (c.find(x) != c.end())
    #define pw(x) (1LL << (x))
    #define ibit(x,i) (((x) >> (i)) & 1)
    #define preturn(...) {out(__VA_ARGS__); return;}
    #define data(v) v.data(), sz(v) // vi -> vai
    #define gtime() ((double(clock()) - 0)/CLOCKS_PER_SEC)

    typedef stringstream sstr;
    typedef long long ll;
    typedef pair<int, int> pii;
    typedef pair<ll,ll> pll;
    typedef vector<int> vi;
    typedef vector<ll> vll;
    typedef vector<pii> vpii;
    typedef vector<vi> vvi;
    typedef vector<vll> vvll;
    typedef valarray<int> vai;
    template <class T>
    using min_pq = priority_queue<T, vector<T>, greater<T>>;
    template <class T>
    using vc = vector<T>;
    template <class T>
    using vvc = vector<vc<T>>;
    template <class T>
    using vvvc = vector<vvc<T>>;
    template <class T>
    using vvvvc = vector<vvvc<T>>;
    template <class T>
    using vvvvvc = vector<vvvvc<T>>;

    template<class F>
    struct y_comb{
        F f;
        template<class T> explicit y_comb(T &&f_in): f(forward<T>(f_in)){ }
        template<class ...Args> decltype(auto) operator()(Args &&...args){ return f(ref(*this), forward<Args>(args)...); }
    };
    template<class F>
    decltype(auto) yf(F &&f){
        return y_comb<decay_t<F>>(forward<F>(f));
    }

    inline int ni(){ int x; cin >> x;   return x; }
    inline ll  nl() { ll  x; cin >> x; return x; }

    template <class T> void mmin(T& a, const T& b) {
        a = (a) < (b) ? (a) : (b);
    }
    template <class T> void mmax(T& a, const T& b) {
        a = (a) > (b) ? (a) : (b);
    }
    template <class T> int LB(vc<T> &a, T x){
        return int(lower_bound(all(a), x) - a.begin());
    }
    template <class T> int UB(vc<T> &a, T x){
        return int(upper_bound(all(a), x) - a.begin());
    }
    template <class T> T MAX(vc<T> &a, int l=0, int r=-1){
        if(r < 0) r = sz(a);
        return *max_element(a.begin()+l, a.begin()+r);
    }
    template <class T> T MIN(vc<T> &a, int l=0, int r=-1){
        if(r < 0) r = sz(a);
        return *min_element(a.begin()+l, a.begin()+r);
    }
    template <class T> auto vv(int d1, T x){
        return vc<T>(d1, x);
    }
    template <class T> auto vv(int d1, int d2, T x){
        return vc<vc<T>>(d1, vc<T>(d2, x));
    }
    template <class T> auto vv(int d1, int d2, int d3, T x){
        return vc<vc<vc<T>>>(d1, vv(d2, d3, x));
    }
    template <class T> auto vv(int d1, int d2, int d3, int d4, T x){
        return vc<vc<vc<vc<T>>>>(d1, vv(d2, d3, d4, x));
    }
    void outv(auto &v){
        for(auto &x: v) {cout<< x <<" ";} cout<<endl;
    }
    void rvec(int &n, auto &v){
        cin >> n; v.resize(n); for(auto &x: v) cin >> (x);
    }
   template<class T, class S> istream& operator>> (istream& in, pair<T, S> &p) {
        cin >> p.first >> p.second;
        return in;
    }
    template<class T> istream& operator>> (istream& in, vector<T>& v) {
        lassert(!v.empty()); for(T &x: v) cin >> x;
        return in;
    }
    template <class Arg, class... Args>
    void read(Arg&& arg, Args&&... args){
        cin >> std::forward<Arg>(arg); using expander = int[];
        (void)expander{0, (void(cin >> std::forward<Args>(args)),0)...};
    }
    template <class Arg, class... Args>
    void out(Arg&& arg, Args&&... args){
        cout << std::forward<Arg>(arg); using expander = int[];
        (void)expander{0, (void(cout << " " << std::forward<Args>(args)),0)...};
        cout << endl;
    }
    namespace tuple_utils{
        template<class ...Ts, size_t ...Is>
        ostream& println_tuple_impl(ostream& os, tuple<Ts...> tuple, index_sequence<Is...>){
            static_assert(sizeof...(Is)==sizeof...(Ts),"Indices must have same number of elements as tuple types!");
            static_assert(sizeof...(Ts)>0, "Cannot insert empty tuple into stream.");
            auto last = sizeof...(Ts) - 1; // assuming index sequence 0,...,N-1
            return ((os << get<Is>(tuple) << (Is != last ? ", " : ")")),...);
        }
    }
    template<class ...Ts> ostream& operator<<(ostream& os, const tuple<Ts...> & tuple) {
        os << "(";
        return tuple_utils::println_tuple_impl(os, tuple, index_sequence_for<Ts...>{});
    }
    template <class Integer, class F>
    Integer find_first_false(Integer l, Integer r, F&& f) {
        --l; // ++r;
        while (r - l > 1) {
            Integer m = midpoint(l, r);
            if (f(m)) l = m;
            else r = m;
        }
        return r;
    }
    template <class Integer, class F>
    Integer find_last_true(Integer l, Integer r, F &&f) {
        return find_first_false(l, r, [&f](Integer i) { return f(i); }) - 1;
    }
    template <class Integer, class F>
    Integer find_first_true(Integer l, Integer r, F &&f) {
        return find_first_false(l, r, [&f](Integer i) { return !f(i); });
    }
    template <class T, class F>
    T last_true(T lo, T hi, F&& f) { 
        lo--; // if all are false, return lo-1
        while(lo < hi){
            T mid = lo + (hi - lo + 1) / 2;
            if(f(mid)) lo = mid; 
            else hi = mid - 1;
        }
        return lo;
    }
    template <class T, class F>
    T first_true(T lo, T hi, F&& f) { 
        // return last_true(lo, hi, [&](T x){ return !f(x); }) + 1;
        hi++; // if all are false, return hi+1
        while(lo < hi){
            T mid = lo + (hi - lo) / 2;
            if(f(mid)) hi = mid; 
            else lo = mid + 1;
        }
        return lo;
    }

    ll pwr(ll base, ll p, ll mod){
        ll ans=1; while(p) {if(p&1) ans=(ans*base)%mod;
            base=(base*base)%mod; p/=2;}
        return ans;
    }
    ll gcd(ll a, ll b) {  return b == 0 ? a : gcd(b,a%b); }
    ll lcm(ll a, ll b) {  return a*(b/gcd(a,b)); }
    ll isqrt (ll x) {
        ll ans = sqrt(x)+2; while(ans*ans>x) ans--;
        return ans;
    }

    string yes(bool t = 1) { return t ? "YES" : "NO"; }
    string no(bool t = 1) { return yes(!t); }
    void pyes(bool t = 1) { out(yes(t)); }
    void pno(bool t = 1) { out(no(t)); }
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    const long double PI = (long double)(3.1415926535897932384626433832795);
    const ll  mx_ll   = numeric_limits<ll> :: max();
    const int mx_int  = numeric_limits<int> :: max();
    const int oo = 0x3f3f3f3f;
    const ll  OO = 0x3f3f3f3f3f3f3f3fll;
    const double eps = 1e-9;
    const int DX[8]={0,1, 0,-1,-1,1,-1, 1};
    const int DY[8]={1,0,-1, 0,-1,1, 1,-1};


bool MULTIPLE_TESTS = 0;
const int maxn = 2e5 + 3;
const int mod = 1e9+7;
void _build(){}

int best_path_slow(int n, int target, int edges[][2], int weights[]) {
    vc<vpii> g(n);
    forn(i,n-1) {
        int x = edges[i][0], y = edges[i][1], w = weights[i];
        g[x].eb(y, w);
        g[y].eb(x, w);
    }
    int ans = n+1;
    auto dp = vv(n, map<ll, int>());
    auto check = [&](int x, auto new_total_path, int new_cnt) {
        if(new_total_path == target) mmin(ans, new_cnt);
        if(dp[x].count(target - new_total_path))
            mmin(ans, new_cnt + dp[x][target - new_total_path]);
    };
    auto add = [&](int x, auto new_total_path, int new_cnt) {
        if(!dp[x].count(new_total_path)) dp[x][new_total_path] = new_cnt;
        else mmin(dp[x][new_total_path], new_cnt);
    };
    auto dfs = yf([&](auto f, int x, int p) -> void {
        add(x, 0, 0);
        for(auto [y, w]: g[x]) if(y != p) {
            f(y, x);
            for(auto [total_path, cnt]: dp[y]) {
                auto new_total_path = total_path + w;
                int new_cnt = cnt + 1;
                check(x, new_total_path, new_cnt);
            }
            for(auto [total_path, cnt]: dp[y]) {
                auto new_total_path = total_path + w;
                int new_cnt = cnt + 1;
                add(x, new_total_path, new_cnt);
            }
        }
    }); dfs(0, -1);
    if(ans > n) ans = -1;
    return ans;
}

int best_path(int n, int target, int edges[][2], int weights[]) {
    assert(target > 0);
    vc<vpii> g(n);
    forn(i,n-1) {
        int x = edges[i][0], y = edges[i][1], w = weights[i];
        assert(w > 0);
        g[x].eb(y, w);
        g[y].eb(x, w);
    }
    int ans = n+1;
    auto dp = vv(n, map<ll, int>());
    vll delta(n);
    auto check = [&](int x, auto new_total_path, int new_cnt) {
        if(new_total_path + delta[x] == target) mmin(ans, new_cnt);
        if(dp[x].count(target - new_total_path - 2*delta[x]))
            mmin(ans, new_cnt + dp[x][target - new_total_path - 2*delta[x]]);
    };
    auto add = [&](int x, auto new_total_path, int new_cnt) {
        if(!dp[x].count(new_total_path)) dp[x][new_total_path] = new_cnt;
        else mmin(dp[x][new_total_path], new_cnt);
    };
    auto dfs = yf([&](auto f, int x, int p) -> void {
        assert(delta[x] == 0);
        // add(x, 0, 0);
        for(auto [y, w]: g[x]) if(y != p) {
            recur_depth++;
            f(y, x);
            recur_depth--;
            if(sz(dp[y]) > sz(dp[x])) {
                debug4(delta[x], dp[x], delta[y], dp[y]);
                swap(delta[x], delta[y]);
                swap(dp[x], dp[y]);
                delta[x] += w;
                delta[y] -= w;
                debug4(delta[x], dp[x], delta[y], dp[y]);
            }
            // if(sz(dp[y]) > sz(dp[x])) {
            //     debug4(delta[x], dp[x], delta[y], dp[y]);



            //     map<ll, int> nx;
            //     for(auto [total_path, cnt]: dp[x]) {
            //         // total_path += delta[x];
            //         // total_path -= delta[y] + w;
            //         nx[total_path + delta[x] - (delta[y] - w*1)] = cnt;
            //     }

            //     // delta[x] = delta[y] + w;
            //     // delta[y] = delta[y] + w;
            //     swap(dp[x], dp[y]); // dp[x] = dp[y];
            //     swap(dp[y], nx); // dp[y] = nx;
            //     // dp[x] = nx;
            //     swap(delta[x], delta[y]);
            //     delta[x] += w;
            //     delta[y] -= w;


            //     // swap(dp[x], dp[y]);
            //     // swap(delta[x], delta[y]);
            //     debug4(delta[x], dp[x], delta[y], dp[y]);
            // }
            assert(sz(dp[y]) <= sz(dp[x]));
            vc<pair<ll, int>> ps;
            
            
            for(auto [total_path, cnt]: dp[y]) {
                ps.eb(total_path + w + delta[y] - delta[x], cnt + 1);
            } ps.eb(0 + w + delta[y] - delta[x], 0 + 1);
            // debug5(x, y, w, delta[x], ps);
            for(auto [new_total_path, new_cnt]: ps) check(x, new_total_path, new_cnt);
            for(auto [new_total_path, new_cnt]: ps) if(new_cnt) add(x, new_total_path, new_cnt);
        }
        // assert(dp[x].count(-delta[x]));
        // swap(dp[x][0], dp[x][-delta[x]]);
        debug3(x, delta[x], dp[x]);
    }); dfs(0, -1);
    if(ans > n) ans = -1;
    return ans;
}

void _solve(){
    int n, target; read(n, target);
    int edges[maxn][2]; 
    int weights[maxn];
    
    forn(i,n-1) {
        read(edges[i][0], edges[i][1], weights[i]);
    }
   
    int ans = best_path(n, target, edges, weights);
    // int slow = best_path_slow(n, target, edges, weights);
    // debug2(ans, slow);
    out(ans);
}


/*************************************************************************/

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