Submission #666915

#	Time	Username	Problem	Language	Result	Execution time	Memory
666915		Bogdan1110	Race (IOI11_race)	C++14	9 / 100	97 ms	52692 KiB

race

#include <bits/stdc++.h>
#include "race.h"
#define FAST {ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
#define FILES {freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);}
#define ll long long
#define ull unsigned long long
#define pqueue priority_queue
#define pb push_back
#define fi first
#define se second
#define ld long double
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(a) (a).begin(), (a).end()
#define mp make_pair 
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key -> # less than k
// find_by_order -> k-th element
// pq max element

const double eps = 0.00000001;
const int NMAX = 2000010;
const ll inf = LLONG_MAX/3;
const ll modi = 998244353;

int K;
int visited[NMAX];
vector<pii>al[NMAX];
ll res = INT_MAX;
map<ll,ll> dfs(ll node, ll dep, ll kol) {
    map<ll,ll>r;
    r[kol] = dep;
    if ( visited[node] ) {
        return r;
    }
    visited[node] = 1;
    for (auto u : al[node]) {
        if ( visited[u.fi] ) continue;
        map<ll,ll>t = dfs(u.fi, dep+1, kol + u.se);
        if ( t.size() > r.size() ) swap(t,r);

        for (auto k:t) {
            if ( r.find(k.fi) != r.end() ) {
                r[k.fi] = min(r[k.fi], k.se);
            }
            else {
                r[k.fi] = k.se;
            }
        }
    }
    if ( r.find(kol+K) != r.end() )
    res = min(res, r[kol+K] - dep);
    //cout << node << ' ' << dep << ' '<< kol << endl;
    return r;
}

int best_path(int n, int k, int h[][2], int l[])
{
    K = k;
    for (int i = 0 ; i < n-1 ; i++ ) {
        al[h[i][0]].pb({h[i][1],l[i]});
        al[h[i][1]].pb({h[i][0],l[i]});
    }

    for (int i = 0; i < n ; i++ ) {
        if ( al[i].size() == 1 ) {
            dfs(i,0,0);
            break;
        }
    }
    if ( res == INT_MAX) return -1;
    return res;
}

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