Submission #1186185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186185		nikaa123	Race (IOI11_race)	C++20	43 / 100	3094 ms	66180 KiB

race

#pragma GCC optimize("Ofast")
#pragma GCC optimize ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#include "race.h"
#include <bits/stdc++.h>
using namespace std;

// #define ll long long
#define pb push_back
#define endl '\n'
#define ff first
#define ss second

typedef vector<int> vii;
typedef pair<int,int> pii;

const int inf = INT_MAX;

const int N = 2e5 + 5;

int n,k,a,b,c;
map <pii,int> l;
int sz[N],fix[N],dead[N];
vector <vii> v(N);
int s,u;
int len;
vector <vii> lst(N);
int ans;
vector <int> 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, int 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 <int>(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