Submission #199941

#	Time	Username	Problem	Language	Result	Execution time	Memory
199941		sans	Race (IOI11_race)	C++14	100 / 100	509 ms	104312 KiB

race

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

#define sp ' '
#define endl '\n'
#define st first
#define nd second
#define sz(x) ((long long int)x.size())
#define pb push_back
#define pob pop_back
#define mp make_pair
#define forn(YY, yy) for(long long int yy = 0; yy < YY; ++yy)
#define prn(XX) cout << XX << '\n'
#define prs(XX) cout << XX << " "
#define TEST cout << "TEST\n";

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;

const long long int MOD = 1e9 + 7;
const long long int INF = 2e9 + 13;
const long long int mINF = -2e9 - 13;
const double PI = acos(-1.0);
const double EPS = 1e-9;

ll mx(ll x, ll y){ return (x>y?x:y); }
ll mn(ll x, ll y){ return (x<y?x:y); }

void max_self(ll &x, ll y){ x = mx(x, y); }
void min_self(ll &x, ll y){ x = mn(x, y); }
void add(ll &x, ll y){ x += (y%MOD); x %= MOD; }
void mul(ll &x, ll y){ x%=MOD; x *= (y%MOD); x %= MOD; }

ll us(ll n, ll x, ll m){
    if(x == 0) return 1;
    ll a = us(n, x>>1, m);
    return (((a*a)%m)*(x&1?n:1))%m;
}

vvpll AdjList;
vll dep;
vector<set<pll>> s;
ll n, k, res = INF;

void dfs(ll u, ll par, ll cur){
    forn(sz(AdjList[u]), i){
        ll v = AdjList[u][i].st, w = AdjList[u][i].nd; 
        if(v == par) continue;

        dep[v] = dep[u]+1;
        dfs(v, u, cur + w);

        auto itr = s[v].lower_bound(mp(cur+k, -1));
        if(itr != s[v].end() and (*itr).st == cur+k){
            res = mn(res, (*itr).nd - dep[u]);
            //cout << "Node " << u << " nun altinda benden" << cur+k << " uzaklikta var.\n";
        }
        if(sz(s[v]) > sz(s[u])){ swap(s[v], s[u]); }

        for(itr = s[v].begin(); itr != s[v].end(); ++itr){
            pll p = *itr;
            auto it = s[u].lower_bound(mp(k+2*cur-p.st, -1));
            if(it != s[u].end() and (it->st) == k+2*cur-p.st){
                res = mn(res, (it->nd)+p.nd-2*dep[u]);
                //cout << "Ben " << u << "yum. Iki nodeum {" <<  itr->st << sp << itr->nd << "} {" << it->st << sp << it->nd << "}\n";
            }
        }
        for(auto itr = s[v].begin(); itr != s[v].end(); ++itr) s[u].insert(*itr);
    }
    auto itr = s[u].lower_bound(mp(cur+k, -1));
    if(itr != s[u].end() and (*itr).st == cur+k) res = mn(res, (*itr).nd);
    s[u].insert(mp(cur, dep[u]));
    return;
}

int best_path(int N, int K, int H[][2], int L[]){
    n = N, k = K;
    AdjList.resize(n);
    dep.resize(n);
    s.resize(n);
    forn(n-1, i){
        AdjList[H[i][0]].pb(mp(H[i][1], L[i]));
        AdjList[H[i][1]].pb(mp(H[i][0], L[i]));
    }
    dfs(0, -1, 0);
    return (res>=2e9?-1:res);
}

/*int main(int argc, char** argv){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    //freopen("race.gir", "r", stdin);
    //freopen("race.cik", "w", stdout);

    cin >> n >> k;
    AdjList.resize(n);
    dep.resize(n);
    s.resize(n);
    forn(n-1, i){
        ll u, v, w;
        cin >> u >> v >> w;
        AdjList[u].pb(mp(v, w));
        AdjList[v].pb(mp(u, w));
    }
    dfs(0, -1, 0);
    cout << ((res>=2e9)?-1:res) << endl;

    return 0;
}*/

//cikisir

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