Submission #481253

#	Time	Username	Problem	Language	Result	Execution time	Memory
481253		kamalsharmaa9	Race (IOI11_race)	C++14	0 / 100	11 ms	14412 KiB

race

#include<bits/stdc++.h>
#include <cstdio>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define N              200005
#define ff              first
#define ss              second
#define int         long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)



int n_ini;
int k;
int fin_ans;
map<int, int>edge[N];
vector<int>gr[N];
int sz[N];
int dp[1000005];
int par[N];
bool vis[N];
void init_all(int n)
{
  for (int i = 0; i <= n; i++)
    gr[i].clear(), par[i] = 0, vis[i] = 0, sz[i] = 0, dp[i] = inf;

}
int init_size(int node, int p)
{
  if (vis[node] == 1)
    return 0;
  int ans = 0;
  for (auto child : gr[node])
  {
    if (child != p)
    {
      ans += init_size(child, node);
    }
  }
  return sz[node] = ans + 1;
}
int get_centroid(int node, int p, int n)
{

  for (auto child : gr[node])
  {
    if ((!vis[child]) && child != p)
    {
      if (sz[child] > n / 2)
        return get_centroid(child, node, n);
    }
  }
  return node;
}
void make_inf(int node, int par, int val)
{
// cout << node << endl;
  //cout << "node\n";
  if (val > k)
    return;
  dp[k - val] = inf;
  for (auto child : gr[node])
  {
    if ((vis[child] == 0) && child != par)
    {
      make_inf(child, node, val + edge[node][child]);
    }
  }
}
void dfs(int node, int par, int d, int num_node)
{

  int need = k - d;
  //cout << node << " " << need << " " << num_node << " " << dp[need] << " " << fin_ans << endl;
  if (need >= 0)
    fin_ans = min(fin_ans, num_node + dp[need]);
  else
    return;
  for (auto child : gr[node])
  {
    if ((vis[child] == 0) && (par != child))
    {

      dfs(child, node, d + edge[node][child], num_node + 1);

    }
  }
}
void dfs2(int node, int par, int d, int num_node)
{
  if (d > k)
    return;
  dp[d] = min(dp[d], num_node);

  for (auto child : gr[node])
  {
    if ((vis[child] == 0) && (child != par))
      dfs2(child, node, d + edge[node][child], d + 1);
  }
}
void init_centroid(int node, int p)
{

  init_size(node, 0);
  int c = get_centroid(node, 0, sz[node]);
  vis[c] = 1;
  par[c] = p;
  make_inf(c, 0, 0);

  dp[0] = 0;
  //cout << c << " ->" << fin_ans << " fin_ans" << endl;
  for (auto child : gr[c])
  {
    //cout << child << " " << vis[child] << endl;
    if (vis[child] == 0)
    {
      dfs(child, c, edge[c][child], 1);
      dfs2(child, c, edge[c][child], 1);
    }
  }

//  make_inf(c, 0, 0);

  for (auto child : gr[c])
  {
    if (!vis[child])
    {
      // cout << "comr\n";
      init_centroid(child, c);
    }
  }

}

int32_t best_path(int32_t n, int32_t b, int32_t H[][2], int32_t L[])
{
  k = (int) b;
  n_ini = (int)n;
  fin_ans = inf;
  init_all(n_ini);
  for (int i = 0; i < n - 1; i++)
  {
    int a, b, c;
    a = (int)H[i][0]; b = (int) H[i][1]; c = (int) L[i];
    a++; b++;
    gr[a].pb(b);
    gr[b].pb(a);
    edge[a][b] = (int)c;
    edge[b][a] = (int)c;

  }

  init_centroid(1, 0);
  if (fin_ans >= inf)
    return -1;
  else
    return (int32_t)fin_ans;

}

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