Submission #764062

#	Time	Username	Problem	Language	Result	Execution time	Memory
764062		Ryuga_	Race (IOI11_race)	C++17	100 / 100	197 ms	82132 KiB

race

#ifdef IS_DEBUG
#pragma ide diagnostic ignored "hicpp-signed-bitwise"
#pragma ide diagnostic ignored "cert-err58-cpp"
#pragma ide diagnostic ignored "cppcoreguidelines-pro-type-member-init"
#pragma ide diagnostic ignored "bugprone-reserved-identifier"
#endif
 
#include <bits/stdc++.h>
#include <bits/extc++.h>
 
#ifndef IS_DEBUG
#define dout false && cout
#endif
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define memset0(x,i) memset(x,i,sizeof(x))
#define count1 __builtin_popcount
#define lead0 __builtin_clz
#define trail0 __builtin_ctz
#define min(...) _min(__VA_ARGS__)
#define max(...) _max(__VA_ARGS__)
#define FOR(i,l,r) for(int i=l;i<r;++i)
#define FORe(i,l,r) for(int i=l;i<=r;++i)
#define ROF(i,l,r) for(int i=r-1;i>=l;--i)
#define ROFe(i,l,r) for(int i=r;i>=l;--i)
#define trav(a,v) for(auto&a:v)
using ll = long long;
using vi = vector<int>;
using pii = pair<int,int>;
using db = double;
using ld = long double;
template<size_t x>struct lg2{enum{v=1+lg2<(x>>1)>::v};};template<>struct lg2<0>{enum{v=0};};
inline ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
inline ll cdiv(ll a,ll b){return a/b+((a^b)>0&&a%b);}
inline ll fdiv(ll a,ll b){return a/b-((a^b)<0&&a%b);}
bool prime(int n){if(n%2==0||n%3==0)return false;for(int i=5;i*i<=n;i+=6)if(n%i==0||n%(i+2)==0)return false;return true;}
template<class T>using set2 = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T1,class T2>using map2 = tree<T1,T2,less<T1>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T>using heap = __gnu_pbds::priority_queue<T,greater<T>,pairing_heap_tag>;
template<class T>using max_heap = __gnu_pbds::priority_queue<T,less<T>,pairing_heap_tag>;
template<class T1,class T2>using unordered_map2 = gp_hash_table<T1,T2>;
template<class T1,class T2>unordered_map2<T1,T2> unordered_map2_size(int exp2){
    return unordered_map2<T1,T2>({},{},{},{},{(uint32_t)1<<exp2});}
template<class T>using unordered_set2 = unordered_map2<T,null_type>;
template<class T>unordered_set2<T> unordered_set2_size(int exp2) {return unordered_map2_size<T,null_type>(exp2);}
template<class T>constexpr const T&_min(const T&x,const T&y){return x<y?x:y;}
template<class T>constexpr const T&_max(const T&x,const T&y){return x<y?y:x;}
template<class T,class...Ts>constexpr const T&_min(const T&x,const Ts&...xs){return _min(x,_min(xs...));}
template<class T,class...Ts>constexpr const T&_max(const T&x,const Ts&...xs){return _max(x,_max(xs...));}
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);
template<class T> void re(T& x) { cin >> x; }
void re(db& d) { string t; re(t); d = stod(t); }
void re(ld& d) { string t; re(t); d = stold(t); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }
template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.fi,p.se); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }
template<class A> void pr(A x) { cout << x; }
template<class H, class... T> void pr(const H& h, const T&... t) { pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { pr(h); if (sizeof...(t)) pr(" "); ps(t...); }
void setIO(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
#ifdef IS_DEBUG
    freopen("../input.txt", "r", stdin);
#endif
}
namespace std{template<class T1,class T2> struct hash<pair<T1,T2>>{
        size_t operator()(const pair<T1,T2>&p)const{return 31*hash<T1>{}(p.fi)+hash<T2>{}(p.se);}
    };}
template<class T>struct BIT{
    T n,*a;
    T sum(int i){T s=0;for(i++;i>0;i-=i&-i)s+=a[i];return s;}
    void edit(int i,T x){for(i++;i<=n;i+=i&-i)a[i]+=x;}
    void init(int m){n=m;a=new T[n+1]();}
    void init(T*arr,int m){init(m);FOR(i,0,n)edit(i,arr[i]);}
    BIT()=default;BIT(T*arr,int m){init(arr,m);}~BIT(){delete[]a;}
};
//endregion
 
struct T {
    unordered_map2<int, int> t;
    int k1 = 0;
    int k2 = 0;
    int size() {
        return t.size();
    }
    int get(int a) {
        auto it = t.find(a - k1);
        if (it != t.end()) {
            return it->se + k2;
        }
        else {
            return -1;
        }
    }
    void insert(int a, int b) {
        auto it = t.find(a - k1);
        if (it != t.end()) {
            it->se = min(it->se, b - k2);
        }
        else {
            t[a - k1] = b - k2;
        }
    }
    void swap(T &other) {
        std::swap(k2, other.k2);
        std::swap(k1, other.k1);
        t.swap(other.t);
    }
};
 
const int MaxN = 200001;
int N, K;
vector<pii> adj[MaxN];
int best = INT_MAX;
 
T dfs(int a, int p) {
    T t;
    t.insert(0, 0);
    trav(e, adj[a]) {
        int b = e.fi;
        int l = e.se;
        if (b == p) continue;
        T t1 = dfs(b, a);
        t1.k1 += l;
        t1.k2++;
        if (t1.size() > t.size()) {
            t.swap(t1);
        }
        trav(x, t1.t) {
            int len = x.fi + t1.k1;
            int score = x.se + t1.k2;
            int result = t.get(K - len);
            if (result != -1) {
                best = min(best, result + score);
            }
        }
        trav(x, t1.t) {
            int len = x.fi + t1.k1;
            int score = x.se + t1.k2;
            if (len < K) {
                t.insert(len, score);
            }
        }
    }
    return t;
}
 
int best_path(int _N, int _K, int H[][2], int L[]) {
    N = _N;
    K = _K;
    FOR(i, 0, N-1) {
        int a = H[i][0];
        int b = H[i][1];
        adj[a].eb(b, L[i]);
        adj[b].eb(a, L[i]);
    }
    dfs(0, 0);
    if (best == INT_MAX)
        best = -1;
    return best;
}

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