Submission #598084

#	Time	Username	Problem	Language	Result	Execution time	Memory
598084		mayureshpatle	Race (IOI11_race)	C++17	100 / 100	476 ms	106232 KiB

race

/**************************************************************
Submitted By: Mayuresh N. Patle
Written On: Saturday, July 16, 2022
**************************************************************/
#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define mod1 998244353
#define rep(i,s,e) for(i=s;i<e;++i)
#define repr(i,s,e) for(i=s;i>e;--i)
#define fp(i) fixed<<setprecision(i)
#define in(a) for(auto &ghe:a) cin>>ghe;
#define in2d(a) for(auto &ghe:a) for(auto &he:ghe) cin>>he;
#define out(a) for(auto &ghe:a) cout<<ghe<<" ";cout<<endl;
#define out2d(a) {for(auto &he:a) {out(he)}}
#define loop(i,a) for(auto &i:a)
#define inrange(i,j,k) (((i)<=(j)) && ((j)<(k)))
#define make(a,i) memset(a,i,sizeof(a))
#define chk(x) cerr<<(#x)<<":"<<(x)<<endl;
#define chk2(x,y) cerr<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<endl;
#define chk3(x,y,z) cerr<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<(#z)<<":"<<(z)<<endl;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector <ll> vll;
typedef vector <float> vf;
typedef vector <ld> vld;
#define pb push_back
#define pob() pop_back()
typedef pair <ll,ll> pll;
#define F first
#define S second
#define mp(a,b) make_pair(a,b)
typedef vector <pll> vp;
typedef vector <bool> flags;
#define all(v) begin(v),end(v)
#define amin(var, val) var = (val)<var ? (val) : var
#define amax(var, val) var = (val)>var ? (val) : var
#define xiny(x,y) (y.find(x)!=y.end())

const ll maxN = 2e5+1;

class edge{
    public:
    ll u,v,w;
    edge(){}
    edge(ll u, ll v, ll w): u(u), v(v), w(w){}
    ll op(ll x) {return u^v^x;}
};

vll G[maxN];
vector <edge> e;
map <ll, ll> m[maxN];
ll k;

pll dfs(ll v, ll p, int& ans)
{
    ll da=0, la=0;
    m[v][0] = 0;
    loop(i, G[v])
    {
        if(ans==1) return {0,0};
        ll u=e[i].op(v), w=e[i].w;
        if(u==p) continue;

        if(w==k)
        {
            ans=1;
            return {0,0};
        }

        pll res = dfs(u, v, ans);

        ll cda = w + res.F;
        ll cla = 1 + res.S;

        if(m[u].size()>m[v].size())
        {
            swap(m[u], m[v]);
            swap(da, cda);
            swap(la, cla);
        }

        loop(p, m[u])
        {
            ll rd = p.F + cda;
            ll rl = p.S + cla;
            if(rd == k) amin(ans, rl);
            else if(rd < k)
            {
                ll reqd = k - rd - da;
                if(xiny(reqd, m[v])) amin(ans, rl + m[v][reqd] + la);
            }
        }

        loop(p, m[u])
        {
            ll rd = p.F + cda;
            ll rl = p.S + cla;
            if(rd < k)
            {
                rd -= da;
                rl -= la;
                if(xiny(rd, m[v])) amin(m[v][rd], rl);
                else m[v][rd] = rl;
            }
        }
    }
    return {da, la};
}


int best_path(int n, int K, int H[][2], int L[])
{
    k=K;
    ll i;
    rep(i,0,n-1)
    {
        ll u=H[i][0], v=H[i][1], w=L[i];
        G[u].pb(e.size());
        G[v].pb(e.size());
        e.pb(edge(u,v,w));
    }
    int ans = maxN;
    dfs(0, -1, ans);
    if(ans==maxN) ans=-1;
    return ans;
}

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