Submission #349003

#	Time	Username	Problem	Language	Result	Execution time	Memory
349003		Killer2501	Race (IOI11_race)	C++14	100 / 100	582 ms	109292 KiB

race

#include <bits/stdc++.h>
#define pb push_back
#define task "sequence"
#define pll pair<ll, ll>
#define pii pair<ll, pll>
#define fi first
#define se second
using ll = long long;
const long long mod = 1e15+7;
const ll N = 2e5 + 5;
const int base = 350;
using ull = unsigned long long;
using namespace std;
ll n, m, t, k, T, a[N], cnt, ans, u, tong, v, b[N], c[N];
map<ll, ll> mp[N];
vector<pll> kq, adj[N];
void dfs(ll u, ll p, ll hi, ll we)
{
    mp[u][we] = hi;
    for(pll v : adj[u])
    {
        if(v.fi == p)continue;
        dfs(v.fi, u, hi+1, we+v.se);
        if(mp[u].size() < mp[v.fi].size())swap(mp[u], mp[v.fi]);
        for(pll x : mp[v.fi])
        {
            if(mp[u].count(we*2+m-x.fi))ans = min(ans, x.se + mp[u][we*2+m-x.fi] - 2 * hi);
        }
        for(pll x : mp[v.fi])
        {
            //if(v.fi == 2)cout << x.fi + v.se<<'\n';
            if(!mp[u].count(x.fi) || mp[u][x.fi] > x.se)
            {
                mp[u][x.fi] = x.se;
                if(x.fi== m)ans = min(ans, x.se);
            }

        }
        //cout <<u<<" "<< v.fi<<'\n';
    }

    //cout << u << '\n';
    //for(pll x : mp[u])cout << x.fi <<" "<<x.se<<'\n';
}
int best_path(int ni, int mi, int h[][2], int l[])
{
  	n = ni;
  	m = mi;
    //cin >> n >> m;
    for(int i = 0; i < n-1; i ++)
    {
        //cin >> a[i] >> b[i];
        a[i] = h[i][0];
        b[i] = h[i][1];
        c[i] = l[i];
    }
    for(int i = 0; i < n-1; i ++)
    {
        //cin >> k;
        adj[a[i]].pb({b[i], c[i]});
        adj[b[i]].pb({a[i], c[i]});
        //cout << a[i] <<" "<<b[i] <<" "<<k<<'\n';
    }
    ans = mod;
    dfs(0, 0, 0, 0);
    if(ans == mod)ans = -1;
    return ans;
}

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