Submission #650276

#	Time	Username	Problem	Language	Result	Execution time	Memory
650276		hackerbhaiya	Race (IOI11_race)	C++17	21 / 100	3095 ms	42548 KiB

race

#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template<class T> using Tree = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization("unroll-loops")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC optimize("no-stack-protector")
// #define ll __int128
#define ll long long
// #define ll int
#define f(i,a,b) for(ll i=a;i<b;i++)
#define mod 1000000007
// #define mod 998244353 
#define mp make_pair
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define ff first
#define ss second
#define rf(i,a,b) for(ll i=a;i>=b;i--)
#define sc(a) scanf("%lld",&a)
#define pf printf
#define sz(a) (int)(a.size())
#define psf push_front
#define ppf pop_front
#define ppb pop_back
#define pb push_back
#define pq priority_queue
#define all(s) s.begin(),s.end()
#define sp(a) setprecision(a)
#define rz resize
#define ld long double
#define inf (ll)1e18
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define eb emplace_back
const double pi = acos(-1);
ll binpow(ll a, ll b){ll res=1;while(b!=0){if(b&1)res*=a;a*=a;b>>=1;}return res;}
ll binpow(ll a, ll b, ll md){ll res=1;a%=md;if(a==0)return 0;while(b!=0){if(b&1)res*=a,res%=md;a*=a,a%=md;b>>=1;}return res%md;}
 
using namespace std;

const int N=21;
vector<vector<array<ll,2> > > v;
vector<vector<ll> > dp;
vector<ll> dis,val;
vector<map<ll,ll> > m;
int ans,k;

void dfs(ll cur, ll par)
{
    dp[cur][0]=par;
    f(i,0,sz(v[cur]))
    {
        ll node=v[cur][i][0],w=v[cur][i][1];
        if(node!=par)
        {
            dis[node]=1+dis[cur],val[node]=val[cur]+w;
            dfs(node,cur);
        }
    }
}

int kth_ancestor(int node, int k)
{
    f(i,0,N)
    {
        if(k&1)
            node=dp[node][i];
        k>>=1;
    }
    return node;
}
 
int find(int a, int b)
{
    if(dis[a]<dis[b])
        swap(a,b);
    int dif=dis[a]-dis[b];
    a=kth_ancestor(a,dif);
    if(a==b)
        return a;
    rf(i,N-1,0)
    {
        if(dp[a][i]!=dp[b][i])
            a=dp[a][i],b=dp[b][i];
    }
    return dp[a][0];
}

void update(ll num)
{
    if(ans==-1)
        ans=num;
    else
        ans=min(1LL*ans,1LL*num);
}

void merge(map<ll,ll> &a, map<ll,ll> &b, ll &s, ll &d)
{
    if(sz(a)>sz(b))
        a.swap(b);
    for(auto it=b.begin();it!=b.end();it++)
    {
        ll sum=(it->ff),cdis=(it->ss);
        ll rem=s-sum;
        if(a.find(rem)!=a.end())
        {
            ll cdis2=a[rem],tot=cdis+cdis2-2*d;
            update(tot);
        }
    }
    for(auto it=b.begin();it!=b.end();it++)
    {
        ll sum=(it->ff),cdis=(it->ss);
        if(a.find(sum)==a.end())
            a[sum]=cdis;
        else
            a[sum]=min(a[sum],cdis);
    }
    b.clear();
}

void dfs2(int cur, int par)
{
    int req=k+val[cur];
    ll req2=k+2*val[cur];
    f(i,0,sz(v[cur]))
    {
        ll node=v[cur][i][0];
        if(node!=par)
        {
            dfs2(node,cur);
            merge(m[cur],m[node],req2,dis[cur]);
        }
    }
    if(m[cur].find(val[cur])!=m[cur].end())
        m[cur][val[cur]]=min(m[cur][val[cur]],dis[cur]);
    else
        m[cur][val[cur]]=dis[cur];

    if(m[cur].find(req)!=m[cur].end())
        update(m[cur][req]-dis[cur]);
}

int best_path(int n, int K, int h[][2], int l[])
{
    v.clear(),dis.clear(),dp.clear(),m.clear(),val.clear();
    v.rz(n+1),dis.rz(n+1),dp.rz(n+1,vector<ll> (N)),m.rz(n+1),val.rz(n+1);
    k=K;
    f(i,0,n-1)
    {
        ll x=h[i][0],y=h[i][1],w=l[i];
        x++,y++;
        v[x].pb({y,w}),v[y].pb({x,w});
    }
    dfs(1,1),ans=-1;
    f(j,1,N)
    {
        f(i,1,n+1)
            dp[i][j]=dp[dp[i][j-1]][j-1];
    }
    dfs2(1,1);
    return ans;
}

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