Submission #988476

#	Time	Username	Problem	Language	Result	Execution time	Memory
988476		HoriaHaivas	Race (IOI11_race)	C++14	31 / 100	2837 ms	129840 KiB

race

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#include "race.h"

using namespace std;

struct edge
{
    int to;
    int cost;
};

int n,k;
int ans;
bool blocked[200001];
int sz[200001];
int h[200001][2];
int l[200001];
vector<edge> nodes[200001];
unordered_map<int,int> f;

void recalc(int node, int parent)
{
    sz[node]=1;
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to])
        {
            recalc(x.to,node);
            sz[node]+=sz[x.to];
        }
    }
}

int find_centroid(int compsize, int node, int parent)
{
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to] && sz[x.to]>compsize/2)
            return find_centroid(compsize,x.to,node);
    }
    return node;
}

void dfs(int node, int parent, int cost, int len)
{
    if (f.find(k-cost)!=f.end())
    ans=min(ans,len+f[k-cost]);
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to])
            dfs(x.to,node,cost+x.cost,len+1);
    }
}

void update(int node, int parent, int cost, int len)
{
    f[cost]=min(f[cost],len);
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to])
            update(x.to,node,cost+x.cost,len+1);
    }
}

void rem(int node, int parent, int cost)
{
    f[cost]=n+1;
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to])
            rem(x.to,node,cost+x.cost);
    }
}

void solve(int node)
{
    int c,i;
    recalc(node,-1);
    c=find_centroid(sz[node],node,-1);
    blocked[c]=1;
    f[0]=0;
    for (auto x : nodes[c])
    {
        if (!blocked[x.to])
        {
            dfs(x.to,c,x.cost,1);
            update(x.to,c,x.cost,1);
        }
    }
    for (auto x : nodes[c])
    {
        if (!blocked[x.to])
        {
            rem(x.to,c,x.cost);
        }
    }
    for (auto x : nodes[c])
    {
        if (!blocked[x.to])
        {
            solve(x.to);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    int i,j,c,x,y;
    n=N;
    k=K;
    for (i=0;i<=n;i++)
         f[i]=n+1;
    for (i=0; i<n; i++)
    {
        x=H[i][0];
        y=H[i][1];
        x++;
        y++;
        c=L[i];
        nodes[x].push_back({y,c});
        nodes[y].push_back({x,c});
    }
    ans=n+1;
    solve(1);
    if (ans!=n+1)
        return ans;
    else
        return -1;
}

Compilation message (stderr)

race.cpp: In function 'void solve(int)':
race.cpp:80:11: warning: unused variable 'i' [-Wunused-variable]
   80 |     int c,i;
      |           ^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:111:11: warning: unused variable 'j' [-Wunused-variable]
  111 |     int i,j,c,x,y;
      |           ^

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