Submission #479433

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

race

//https://pastebin.com/jVURaNCJ
#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--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;


void c_p_c()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);


}
vector<int>gr[N];
map<int, map<int, int>>edge;
map<int, int>m[N];
int depth[N];
int fin_ans = inf;
int k;
pair<int, int> dfs(int node, int par)
{

  ///cout << node << "++";
  map<int, int>d_val;
  int sz = 0;
  int ind;
  for (auto child : gr[node])
  {
    // cout << child << endl;
    if (child != par )
    {
      //cout << child << endl;
      pii temp = dfs(child, node);
      if (temp.ss > sz)
      {
        sz = temp.second;
        ind = child;
      }
      d_val[child] = temp.ff;

    }
  }

  if (sz == 0) {
    // it is a leaf node
    m[node][0] = 1;

    return {0, 1};
  }

  //
////.. find answer in this subtree like the greatest one
  //
  //int to_find = k - edge[node][ind];
  for (auto child : gr[node])
  {
    if (child == par)
      continue;
    int to_find = k - edge[node][child];
    if (to_find == 0)
      fin_ans = 1;
    if (child != par)
    {
      if (m[child].find(to_find) != m[child].end())
      {

        fin_ans = min(fin_ans, 2 + d_val[child] - m[child][to_find]);
      }
    }
  }
  m[node].swap(m[ind]); int d = d_val[ind] + 1;

  m[node][edge[node][ind]] = d;
  for (auto child : gr[node])
  {
    if (child != par && child != ind)
    {
      // go in this
      for (auto i : m[child])
      {
        int val = i.first + edge[node][child];
        int to_find = k - val;
        if (to_find == 0)
          fin_ans = min(fin_ans, d_val[child] - i.ss + 1);
        if (m[node].find(to_find) != m[node].end())
        {
          // cout << node << " " << to_find << " " << d_val[child] << " " << m[child][i.ff] << endl;

          fin_ans = min(fin_ans, d - m[node][to_find] + 1 + d_val[child] - m[child][i.ff] + 1);
        }
        if (m[node].find(i.first) != m[node].end() && (d - m[node][i.first]) < (d_val[child] - m[child][i.first] + 1))
          m[node][i.ff] = d;
        else
          m[node][i.ff] = d;
      }
    }

  }
//  cout << node << " " << fin_ans << endl;
  return {d, m[node].size()};

}

int best_path(int32_t n, int32_t K, int32_t H[][2], int32_t L[]) {
  int i, j, a, b, c;
  //scanf("%lld%lld",&n,&l);
  k = K;
  for (i = 0; i < n - 1; i++) {
    //scanf("%lld%lld%lld",&a,&b,&c);
    //a++;b++;
    a = H[i][0]; b = H[i][1]; c = L[i];
    a++; b++;
    //cout << a << b << c << endl;
    edge[a][b] = c;
    edge[b][a] = c;
    gr[a].pb(b);
    gr[b].pb(a);
  }
  dfs(1, 0);
  return (int32_t)fin_ans;

}

Compilation message (stderr)

race.cpp: In function 'long long int best_path(int32_t, int32_t, int32_t (*)[2], int32_t*)':
race.cpp:128:10: warning: unused variable 'j' [-Wunused-variable]
  128 |   int i, j, a, b, c;
      |          ^

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