Submission #133106

#	Time	Username	Problem	Language	Result	Execution time	Memory
133106		briansu	Race (IOI11_race)	C++14	100 / 100	887 ms	99960 KiB

race

#include "race.h"

//{
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef double lf;
typedef pair<ll,ll> ii;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define FILL(i,n) memset(i,n,sizeof i)
#define X first
#define Y second
#define SZ(_a) (int)_a.size()
#define ALL(_a) _a.begin(),_a.end()
#define pb push_back
#ifdef brian
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif // brian
//}


const ll MAXn=2e5+5,MAXlg=__lg(MAXn)+2;
const ll MOD=1000000007;
const ll INF=ll(1e9);

namespace pre{
  vector<ii> v[MAXn];
  ii p[MAXn];
  ll lf[MAXn];
  void dfs(ll now, ll f)
  {
    lf[now] = 1;
    for(ii k:v[now])if(k.X  != f)
    {
      p[k.X] = ii(now, k.Y);
      lf[now] = 0;
      dfs(k.X, now);
    }
  }
};

ll ans = INF, n, k;

void cal(vector<ii> &a, vector<ii> &b)
{
  ll it = SZ(b) - 1;
  REP(i, SZ(a))
  {
    while(it >= 0 && a[i].X + b[it].X > k)it --;
    if(it >= 0 && a[i].X + b[it].X == k)ans = min(ans, a[i].Y + b[it].Y);
  }
}

vector<ii> mg(vector<ii> &a, vector<ii> &b, ii d)// merge (a, b + d)
{
  for(auto &p:b)p.X = min(INF, p.X + d.X), p.Y += d.Y;
  vector<ii> c(SZ(a) + SZ(b));
  merge(ALL(a), ALL(b), c.begin());
  vector<ii> ret;
  for(auto &p:c)if(!SZ(ret) || p.X != ret.back().X)ret.pb(p);
  return ret;
}

ll u[MAXn], gct, rt;
ii dis[MAXn];
vector<ll> v[MAXn];
vector<ii> dt[MAXn][2];

#define CLR(_a) (_a).clear(),(_a).shrink_to_fit()

void dfs(ll now)
{
  u[now] = 0;
  for(ll t:v[now])dfs(t);
  if(SZ(v[now]) == 1)
  {
    ll t = v[now][0];
    if(u[t] || now == rt)return;
    u[t] = u[now] = 1;
    gct --;
    cal(dt[t][0], dt[now][1]);
    dt[now][0] = mg(dt[now][0], dt[t][0], dis[now]);
    if(SZ(v[t])){
      dt[now][1] = mg(dt[t][1], dt[now][1], dis[t]);
      dis[now] = {dis[now].X + dis[t].X, dis[now].Y + dis[t].Y};
    }
    v[now] = v[t];
    CLR(v[t]);CLR(dt[t][0]);CLR(dt[t][1]);
    return;
  }
  vector<ll> a, b, nv;
  for(ll t:v[now])
  {
    if(u[t])nv.pb(t);
    else if(!SZ(v[t]))a.pb(t);
    else b.pb(t);
  }
  for(int i = 0;i < SZ(a);)
  {
    ll x, y;
    if(i < SZ(b))x = b[i], y = a[i], i ++;
    else if(i < SZ(a) - 1)x = a[i + 1], y = a[i], i += 2;
    else{
      nv.pb(a[i]);
      break;
    }
    u[x] = u[y] = 1;
    gct --;
    nv.pb(x);
    cal(dt[x][0], dt[y][0]);
    dt[x][0] = mg(dt[x][0], dt[y][0], {0, 0});
    if(SZ(v[x]))dt[x][1] = mg(dt[x][1], dt[y][0], dis[x]);
    CLR(v[y]);CLR(dt[y][0]);CLR(dt[y][1]);
  }
  if(SZ(b) > SZ(a))for(int i = SZ(a);i < SZ(b);i ++)nv.pb(b[i]);
  v[now] = nv;
}

int best_path(int N, int K, int H[][2], int L[])
{
  srand(chrono::system_clock::now().time_since_epoch().count());
  k = K;
  n = N;
  REP(i, n - 1)
  {
    pre::v[H[i][0]].pb(ii(H[i][1], L[i]));
    pre::v[H[i][1]].pb(ii(H[i][0], L[i]));
  }
  rt = rand() % n;
  pre::dfs(rt, -1);
  for(int i = 0;i < n;i ++)if(i != rt)
  {
    v[pre::p[i].X].pb(i);
    if(pre::p[i].Y == k)ans = 1;
    dis[i] = {pre::p[i].Y, 1};
    dt[i][0].pb({pre::p[i].Y, 1});
    if(!pre::lf[i])dt[i][1].pb({pre::p[i].Y, 1});
  }
  gct = n - 1;
  ll iter = 0;
  while(gct > 1)
  {
    dfs(rt);
    iter ++;
  }
  debug(iter);
  assert(iter <= 35);
  if(ans == INF)return -1;
  else return ans;
}

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