Submission #936080

#	Time	Username	Problem	Language	Result	Execution time	Memory
936080		vjudge1	Race (IOI11_race)	C++17	0 / 100	7 ms	33328 KiB

race

#include<bits/stdc++.h>
using    namespace std;
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define M   1000000007  //998244353 //
#define ll long long
#define pa pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define pi acos(-1.0)
#define vi vector<int>
#define vll vector<ll>
#define fr(i,n,j) for(i=j;i<=n;i++)
#define rfr(i,n,j) for(i=n;i>=j;i--)
#define ct continue;
#define yo cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define all(v) v.begin(),v.end()
#define endl '\n'
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int ar[500005],br[500005],kk;
vector<pa>adj[500001];
map<ll,map<int,int> > cnt;
ll sz[500005],mx[500005],dist[500005];
int level[500006],ans;
vector<int>sub[500005];
void dfs(int child,int par,int flag)
{
    for(auto u:adj[child])
    {
        if(u.ff==par)ct;
        if(mx[child]==u.ff)ct;
        dfs(u.ff,child,0);
    }
    if(mx[child]!=-1)
    {
        int u=mx[child];
        dfs(u,child,1);
        swap(sub[child],sub[u]);
    }
    sub[child].pb(child);
    cnt[dist[child]][level[child]]++;
    for(auto u:adj[child])
    {
        if(u.ff==par)ct;
        if(mx[child]==u.ff)ct;
        for(auto u1:sub[u.ff])
        {
            sub[child].pb(u1);
            ll tmp=kk+2*dist[child]-dist[u1];
            if(cnt[tmp].size())
            {
                auto it=cnt[tmp].rbegin();
                assert((*it).ss>0);
                ans=min(ans,(*it).ff+level[u1]-2*level[child]);
            }
            cnt[dist[u1]][level[u1]]++;
        }
    }
    if(cnt[dist[child]+kk].size())
    {
        auto it=cnt[dist[child]+kk].rbegin();
        ans=min(ans,(*it).ff-level[child]);
    }
    if(flag==0)
    {
        for(auto u:sub[child])
        {
            cnt[dist[u]][level[u]]--;
            if(cnt[dist[u]][level[u]]==0)cnt[dist[u]].erase(level[u]);
        }
    }
}
void dfs2(int child,int par)
{
    int tmp=0,big=-1;
    sz[child]=0;
    for(auto u:adj[child])
    {
        if(u.ff==par)ct;
        level[u.ff]=level[child]+1;
        dist[u.ff]=dist[child]+u.ss;
        dfs2(u.ff,child);
        if(sz[u.ff]>tmp)tmp=sz[u.ff],big=u.ff;
        sz[child]+=sz[u.ff];
    }
    mx[child]=big;
    sz[child]++;
}
int best_path(int N,int K,int H[][2],int L[])
{
    ll te,n,m,i,j,k,w1,x,y,z,l2,k2,k1,q,l,r;

    n=N,kk=K;
    fr(i,n-2,0)
    {
        x=H[i][0],y=H[i][1],z=L[i];
        adj[x].pb({y,z});
        adj[y].pb({x,z});
    }
    dfs2(0,-1);
    ans=INT_MAX;
    dfs(0,-1,1);
    if(ans>n)ans=-1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:93:8: warning: unused variable 'te' [-Wunused-variable]
   93 |     ll te,n,m,i,j,k,w1,x,y,z,l2,k2,k1,q,l,r;
      |        ^~
race.cpp:93:13: warning: unused variable 'm' [-Wunused-variable]
   93 |     ll te,n,m,i,j,k,w1,x,y,z,l2,k2,k1,q,l,r;
      |             ^
race.cpp:93:17: warning: unused variable 'j' [-Wunused-variable]
   93 |     ll te,n,m,i,j,k,w1,x,y,z,l2,k2,k1,q,l,r;
      |                 ^
race.cpp:93:19: warning: unused variable 'k' [-Wunused-variable]
   93 |     ll te,n,m,i,j,k,w1,x,y,z,l2,k2,k1,q,l,r;
      |                   ^
race.cpp:93:21: warning: unused variable 'w1' [-Wunused-variable]
   93 |     ll te,n,m,i,j,k,w1,x,y,z,l2,k2,k1,q,l,r;
      |                     ^~
race.cpp:93:30: warning: unused variable 'l2' [-Wunused-variable]
   93 |     ll te,n,m,i,j,k,w1,x,y,z,l2,k2,k1,q,l,r;
      |                              ^~
race.cpp:93:33: warning: unused variable 'k2' [-Wunused-variable]
   93 |     ll te,n,m,i,j,k,w1,x,y,z,l2,k2,k1,q,l,r;
      |                                 ^~
race.cpp:93:36: warning: unused variable 'k1' [-Wunused-variable]
   93 |     ll te,n,m,i,j,k,w1,x,y,z,l2,k2,k1,q,l,r;
      |                                    ^~
race.cpp:93:39: warning: unused variable 'q' [-Wunused-variable]
   93 |     ll te,n,m,i,j,k,w1,x,y,z,l2,k2,k1,q,l,r;
      |                                       ^
race.cpp:93:41: warning: unused variable 'l' [-Wunused-variable]
   93 |     ll te,n,m,i,j,k,w1,x,y,z,l2,k2,k1,q,l,r;
      |                                         ^
race.cpp:93:43: warning: unused variable 'r' [-Wunused-variable]
   93 |     ll te,n,m,i,j,k,w1,x,y,z,l2,k2,k1,q,l,r;
      |                                           ^

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