Submission #714065

#	Time	Username	Problem	Language	Result	Execution time	Memory
714065		speedyArda	Race (IOI11_race)	C++14	100 / 100	551 ms	40364 KiB

race

#include "race.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int MAXN = 2e5+5;
vector< vector< pair<ll, int> > > adj(MAXN);
ll ans = -1;
int sz[MAXN];
int par_cent[MAXN];
ll cnt[(int)(1e6+5)];
bool visited[MAXN];
int k;
//int cent;
inline void minimize(ll &a, ll b)
{
    if(a == -1 || a > b)
        a = b;
}

int dfs_sz(int v, int p)
{
  sz[v] = 1;
  for(pair<ll, int> e : adj[v])
  {
    if(e.second == p || visited[e.second])
      continue;
    int tmp = dfs_sz(e.second, v);
    sz[v] += tmp;

  }

  return sz[v];
}

int dfs_cent(int v, int p, int n)
{
    //cout << v << "\n";
    for(pair<ll, int> e : adj[v])
    {
        if(e.second == p || visited[e.second])
          continue;
        if(sz[e.second] * 2 > n)
          return dfs_cent(e.second, v, n);
    }

    return v;
}

void get_cnt(int sum, bool filling, int u, int p = -1, int depth = 1)
{
    if(sum > k) return;
    if(filling)
        minimize(cnt[sum], depth);
    else {
        if(cnt[k - sum] != -1) {
            minimize(ans, depth + cnt[k - sum]);
            //cout << ans << "\n";
        }
    }
    for(auto [C, v]: adj[u]) {
        if(v != p && !visited[v]) get_cnt(sum + C, filling, v, u, depth + 1);
    }
}

void del(int sum, int u, int p = -1)
{
    if(sum > k) return;
    cnt[sum] = -1;
    for(auto [C, v]: adj[u]) {
        if(v != p && !visited[v])
            del(sum + C, v, u);
    }
}

void centroid(int v, int p)
{
    int n = dfs_sz(v, p);
    int cent = dfs_cent(v, p, n);
    //cout << cent << "\n";
    visited[cent] = true;
    cnt[0] = 0;
    for(auto [C, v]: adj[cent]) {
      if(!visited[v]) {
          get_cnt(C, false, v);
          get_cnt(C, true, v);
      }
    }

    for(auto [C,v] : adj[cent])
    {
        if(!visited[v])
        {
          del(C, v);
        }
    }
    for(auto [C, v] : adj[cent])
    {
      if(!visited[v])
        centroid(v, cent);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
  k = K;
  for(int i = 0; i < N - 1; i++)
  {
    adj[H[i][0]].push_back({L[i], H[i][1]});
    adj[H[i][1]].push_back({L[i], H[i][0]});
  }

  memset(cnt, -1, sizeof(cnt));

  centroid(0, -1);

  return ans;
}

Compilation message (stderr)

race.cpp: In function 'void get_cnt(int, bool, int, int, int)':
race.cpp:60:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |     for(auto [C, v]: adj[u]) {
      |              ^
race.cpp: In function 'void del(int, int, int)':
race.cpp:69:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |     for(auto [C, v]: adj[u]) {
      |              ^
race.cpp: In function 'void centroid(int, int)':
race.cpp:82:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |     for(auto [C, v]: adj[cent]) {
      |              ^
race.cpp:89:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |     for(auto [C,v] : adj[cent])
      |              ^
race.cpp:96:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   96 |     for(auto [C, v] : adj[cent])
      |              ^

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