Submission #1186182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186182		nikaa123	Race (IOI11_race)	C++20	43 / 100	3093 ms	60640 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

// #define ll long long
#define eb emplace_back
#define mp make_pair
#define pb push_back
#define pp pop_back
#define endl '\n'
#define ff first
#define ss second
#define stop exit(0)
// #define sz(x) (int)x.size()
#define pause system("pause")
#define all(x) (x).begin(),(x).end()
#define deb(x) cout << #x << "-" << x  << endl

typedef char chr;
typedef string str;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
typedef pair <int,pii> tp;

const long long INF = LLONG_MAX;
const int inf = INT_MAX;
const int mod = 99824435;
const int MOD = 1e9 + 7;
const int dx[] = {0,0,-1,1};
const int dy[] = {-1,1,0,0};
const double PI = 2 * acos(0.0);

const int N = 2e5 + 5;

ll n,k,a,b,c;
map <pii,ll> l;
ll sz[N],fix[N],dead[N];
vector <vii> v(N);
ll s,u;
ll len;
vector <vii> lst(N);
ll ans;
vector <ll> A;

void dfs(int x) {
    sz[x] = 1;
    fix[x] = 1;
    for (auto to:v[x]) {
        if (!fix[to] && !dead[to]) {
            dfs(to);
            sz[x] += sz[to];
        }
    }
}

void dfs1(int x) {
    s++;
    fix[x] = 1;
    for (auto to:v[x]) {
        if (!dead[to] && !fix[to]) {
            dfs1(to);
        }
    }
}

int dfs2(int x, int p) {
    for (auto to:v[x]) {
        if (dead[to] || to == p) continue;
        if (sz[to] > s/2) return dfs2(to,x);
    }
    return x;
}

void dfs3(int x, int p, ll len,int d,vector <pii> &lst) {
    if (len > k) return;
    lst.pb({len,d});
    for (auto to:v[x]) {
        if (dead[to] || to == p) continue;
        dfs3(to,x,len+l[{to,x}],d+1,lst);
    }
}

void solve(int u) {
  A = vector <ll>(k+1,inf);
  A[0] = 0;

  for (auto lw:v[u]) {
      if (dead[lw]) continue;

      vector <pii> lst;
      dfs3(lw,u,l[{lw,u}],1,lst);

      for (auto l:lst) {
          if (l.ff > k) continue;
          if (A[k-l.ff] != inf) ans = min(ans,l.ss+A[k-l.ff]);
      }
      for (auto l:lst) {
          if (l.ff > k) continue;
          A[l.ff] = min(A[l.ff],l.ss);
      }
  }

}

int best_path(int N, int K, int H[][2], int L[]) {

  n=N;
  k = K;
  for (int i = 0; i < n-1; i++) {
    a = H[i][0];
    b = H[i][1];
    c = L[i];
    v[a].pb(b);
    v[b].pb(a);
    l[{a,b}] = c;
    l[{b,a}] = c;
  }
  bool ok = true;
  ans = inf;
  while (ok) {
      ok = false;
      for (int i = 0; i < n; i++) {
          fix[i] = 0;
          sz[i] = 0;
      }
      for (int i = 0; i < n; i++) {
          if (!fix[i] && !dead[i]) dfs(i);
      }
      for (int i = 0; i < n; i++) {
          fix[i] = 0;
      }
      for (int i = 0; i < n; i++) {
          if (!fix[i] && !dead[i]) {
              s = 0;
              dfs1(i);
              u = dfs2(i,-1);
              if (s > 1) {
                  ok = true;                    
                  solve(u);
                  dead[u] = 1; 
              }
          }
      }
  }
  if (ans == inf) ans = -1;
  return ans;
}

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