Submission #333497

#	Time	Username	Problem	Language	Result	Execution time	Memory
333497		Aryan_Raina	Race (IOI11_race)	C++14	21 / 100	3074 ms	8748 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 (1000000009)
#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);
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,-1);
  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,-1);
}
 
int CentroidDecomposition(vector<vii> &g) {
  vector<bool> dead(g.size(),false);
  map<int,int> E, tmp;
  int ans=-1;
  function<void (int,int,int,int)> dfs = [&] (int u, int par, int len, int wt) {
    if (wt>k) return;
    if (tmp.count(wt)) tmp[wt]=min(tmp[wt], len);
    else tmp[wt]=len;
    if (E.count(k-wt)) {
      ans=min(ans,len+E[k-wt]);
      if (ans==-1) ans=len+E[k-wt];
    }
    for (auto v : g[u]) if (!dead[v.F]&&v.F!=par){
      dfs(v.F, u, len+1, wt+v.S);
    }
  };
  function<void (int)> rec = [&] (int start) {
    E.clear(); E[0]=0;
    int c = OneCentroid(start, g, dead);
    dead[c]=true;
    for (auto v : g[c]) if (!dead[v.F]) {
      tmp.clear(); tmp[0]=0;
      dfs(v.F,c,1,v.S);
      for (auto itr : tmp) {
        if (E.count(itr.F)) E[itr.F]=min(E[itr.F], itr.S);
        else E[itr.F]=itr.S;
      }
    }
    for (auto v : g[c]) if (!dead[v.F]) {
      rec(v.F);
    }
    dead[c]=false;
  };
  rec(0);
  return ans;
}
 
int best_path(int nn, int kk, int h[][2], int l[])
{
  n=nn, k=kk;
  vector<vii> g(n);
  FOR(i,n-1) {
    g[h[i][0]].PB({h[i][1],l[i]});
    g[h[i][1]].PB({h[i][0],l[i]});
  }
  int ans = CentroidDecomposition(g);
  return ans;
}

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