Submission #1025231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025231		mindiyak	Race (IOI11_race)	C++17	21 / 100	134 ms	63300 KiB

race

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <string>
#include <iostream>
#include <cmath>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<int, int> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define len(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define nl endl
#define S second
#define lb lower_bound
#define ub upper_bound
#define aint(x) x.begin(), x.end()
#define raint(x) x.rbegin(), x.rend()
#define ins insert
const int MOD = 1000000007;
#include "race.h"

/*
1.BFS numer of children (priority queue with visited)
2.Check children nodes with each other (set with upper and lower bound)
3.Save children distances to the parent node (save a set with distances to each leaf)
 */

vector<vpi> paths(2e5+3,vpi());
vector<map<ll,pair<ll,ll>>> dist(2e5+3,map<ll,pair<ll,ll>>());
vi children(2e5+3);
vi parent(2e5+3,-1);
vl parent_dist(2e5+3,-1);

void dfs(int pos,int prev){
  int sum = 1;
  for(auto node:paths[pos]){
    if(node.F == prev)continue;
    parent[node.F] = pos;
    parent_dist[node.F] = node.S;
    dfs(node.F,pos);
    sum += children[node.F];
  }
  children[pos] = sum;
}

int best_path(int N, int K, int H[][2], int L[])
{
  FOR(i,0,N-1){
    paths[H[i][0]].pb({H[i][1],L[i]});
    paths[H[i][1]].pb({H[i][0],L[i]});
  }

  dfs(0,-1);

  // FOR(i,0,N)cout << children[i] << " ";
  // cout << endl;
  // FOR(i,0,N)cout << parent[i] << " ";
  // cout << endl;
  // FOR(i,0,N)cout << parent_dist[i] << " ";
  // cout << endl;

  priority_queue<pi> pq;
  FOR(i,0,N){
    pq.push({-children[i],i});
  }

  ll ans = 1e18;

  while(!pq.empty()){
    int node = pq.top().S;pq.pop();
    // cout << node << " | " << endl;
    for(auto a:dist[node]){
      // cout << "a " << a.F << " " << K-a.F;
      if(a.F > K)continue;
      if(dist[node].count(K-a.F)){
        // cout << " " << dist[node][K-a.F].S << " " << a.S.S << " " << a.S.F << " " << dist[node][K-a.F].F;
        if(dist[node][K-a.F].S != a.S.S){
          // cout << " ans - " << a.S.F+dist[node][K-a.F].F+1;
          ans = min(ans,a.S.F+dist[node][K-a.F].F+1);
        }
      }
      // cout << endl;
    }

    if(parent[node] == -1)continue;

    
    // cout << "b " << parent[node] << " " << parent_dist[node] << " " << 1 << " " << node  << endl;
    dist[parent[node]].insert({parent_dist[node],{1,node}});
    for(auto a:dist[node]){
      // cout << "c " << parent[node] << " " << parent_dist[node]+a.F << " " << a.S.F+1 << " " << node  << endl;
      if(parent_dist[node]+a.F == K){

        ans = min(ans, a.S.F+2);
      }
      if(parent_dist[node]+a.F >= K)continue;
      dist[parent[node]].insert({parent_dist[node]+a.F,{a.S.F+1,node}});
    }
    // cout << endl;
  }

  if(ans == 1e18)return -1;
  return ans-1;
}

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