Submission #333474

#	Time	Username	Problem	Language	Result	Execution time	Memory
333474		Aryan_Raina	Race (IOI11_race)	C++14	0 / 100	1 ms	364 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;
map<int,pair<int,int>> E;
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);
  int ans=INT_MAX;
  function<void (int,int,int,int)> dfs = [&] (int u, int par, int eused, int wtused) {
    if (E.count(wtused)) {
      if (E[wtused].F==eused) E[wtused].S++;
      else {
        E[wtused].F=min(eused, E[wtused].F); E[wtused].S=1;
      }
    } else E[wtused]={eused,1};
    for (auto v : g[u]) if (!dead[v.F]&&v.F!=par){
      if (wtused+v.F>k) continue;
      dfs(v.F, u, eused+1, wtused+v.S);
    }
  };
  function<void (int)> rec = [&] (int start) {
    E.clear();
    int c = OneCentroid(start, g, dead);
    dead[c]=true;
    dfs(c,-1,0,0);
    REP(i,0,k/2) {
      if (E.count(i)==0||E.count(k-i)==0) continue;
      if (i==k-i&&E[i].S<2) continue;
      ans=min(ans,E[i].F+E[k-i].F);
    }
    for (auto v : g[c]) if (!dead[v.F]) {
      rec(v.F);
    }
    dead[c]=false;
  }; 
  rec(0);
  if (ans==INT_MAX) ans=-1;
  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: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57