Submission #333326

#	Time	Username	Problem	Language	Result	Execution time	Memory
333326		Aryan_Raina	Race (IOI11_race)	C++14	0 / 100	4 ms	4972 KiB

race

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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<ll> vll;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define INF (1<<29)
#define eps (1e-7)
#define MOD (1000000007)
#define mem(arr, val) memset((arr), (int)(val), sizeof (arr))
#define REP(i, a, b) for (int i=a; i<=b; i++)
#define REPn(i, a, b) for (int i=a; i>=b; i--)
#define FOR(i, n) REP(i, 0, n-1)
#define FORn(j, n) REPn(j, n-1, 0)
#define all(v) v.begin(), v.end()
#define allR(v) v.rbegin(), v.rend()
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

const int N=200009;
const int K=1000009;
int n,k;
vector<int> centPar(N), E(K+1);
int OneCentroid(int root, vector<vii> &g, vector<bool> &dead) {
  vi sz(g.size());
  function<void (int,int)> get_sz = [&](int u, int par) {
    sz[u]=1;
    for (auto v : g[u]) if (v.F!=par&&!dead[v.F]) {
      get_sz(v.F,u);
      sz[u]+=sz[v.F];
    }
  };
  get_sz(root,0);
  int n = sz[root];
  function<int (int,int)> dfs = [&](int u, int par) {
    for (auto v : g[u]) if (v.F!=par&&!dead[v.F]) {
      if (sz[v.F]>n/2) return dfs(v.F,u);
    }
    return u;
  };
  return dfs(root,0);
}

int CentroidDecomposition(vector<vii> &g) {
  vector<bool> dead(g.size(),false);
  int ans=-1;
  function<void (int,int,int,int)> dfs = [&] (int u, int par, int eused, int wtused) {
    for (auto v : g[u]) if (!dead[v.F]&&v.F!=par){
      if (wtused+v.S>k) continue;
      if (E[wtused+v.S]==0||E[wtused+v.S]>eused+1) {
        E[wtused+v.S]=eused+1;
      }
      dfs(v.F, u, eused+1, wtused+v.S);
    }
  };
  function<void (int)> rec = [&] (int start) {
    int c = OneCentroid(start, g, dead);
    dead[c]=true;
    for (auto v : g[c]) if (!dead[v.F]) {
      rec(v.F);
    }
    dfs(c,-1,0,0);
    FOR(i,k/2+1) {
      if (E[i]==0||E[k-i]==0) continue;
      if (ans==-1||E[i]+E[k-i]<ans) ans=E[i]+E[k-i];
    }
    dead[c]=false;
    E.clear();
  }; 
  rec(0);
  return ans;
}

int best_path(int nn, int kk, int h[][2], int l[])
{
  n=nn, k=kk;
  vector<vii> g(n+1);
  FOR(i,n-1) {
    g[h[i][0]].PB({h[i][1],l[i]});
    g[h[i][1]].PB({h[i][0],l[i]});
  }
  return CentroidDecomposition(g);
}

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