Submission #685221

#	Time	Username	Problem	Language	Result	Execution time	Memory
685221		cadmiumsky	Race (IOI11_race)	C++14	100 / 100	459 ms	70732 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;

using ll = long long;
#define int ll 

#define sz(x) (x).size()


using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 2e5 + 5, vmax = 1e6 + 5, inf = 1e9 + 5;

struct MN {
  int x, atr;
  MN(int a = inf, int b = -1): x(a), atr(b) {;}
  MN operator += (const MN& a) {
    //if(a.atr == atr)
    #warning idk
      x = min(x, a.x);
    return *this;
  } 
};
struct MN2 {
  MN a, b;
  MN2(MN x = MN(), MN y = MN()): a(x), b(y) {;}
  MN2 operator += (const MN& x) {
    if(x.x < a.x) {
      if(x.atr == a.atr)
        a.x = x.x;
      else {
        b = a;
        a = x;
      }
    }
    else if(x.x < b.x && x.atr != a.atr) {
      b = x;
    }
    return *this;
  }
  int operator()(const MN& x) const {
    return x.x + (x.atr == a.atr? b.x : a.x);
  }
};


vector<pii> g[nmax];

int K;

int mn = nmax;

namespace Centr {
  MN2 freq[vmax];
  vector<tii> lst;
  
  int area[nmax];
  int occ[nmax];
  
  void init(int node, int f) {
    area[node] = 0;
    if(occ[node] == 1) return;
    for(auto [x, e] : g[node]) {
      if(x != f)
        init(x, node),
        area[node] += area[x];
    }
    area[node]++;
    return;
  }
  
  int findcentr(int node, int f, int thresh) {
    
    for(auto [x, e] : g[node]) {
      if(x == f) continue;
      if(occ[x] == 0 && area[x] > thresh) {
        return findcentr(x, node, thresh);
      }
    } 
    return node;
    
  }
  
  void dfs(int node, int f, int atr, int dist, int h = 1) {
    if(dist > K) return;
    if(occ[node] == 1) return;
    lst.emplace_back(dist, h, atr);
    //cerr << node << ' ' << ' ' << f << ' ' << atr << ' ' << dist << ' ' << h << '\n';
    for(auto [x, e] : g[node]) {
      if(x == f) continue;
      dfs(x, node, atr, dist + e, h + 1);
    }
  }
  
  void decomp(int node) {
    init(node, node);
    //cerr << area[node] << ' ';
    node = findcentr(node, node, area[node] / 2);
    //cerr<< area[node] << ' ' << node << '\n';
    
    lst.clear();
    lst.emplace_back(0, 0, node);
    for(auto [x, e] : g[node]) {
      dfs(x, node, x, e);
    }
    //cerr << node << ":\n";
    for(auto [ptr, val, atr] : lst) {
      //cerr << ptr << ' ' << val << ' ' << atr << '\n';
      freq[ptr] += MN(val, atr);
    }
      
    for(auto [ptr, val, atr] : lst) {
      mn = min(mn, freq[K - ptr](MN(val, atr)));
    }
    
    for(auto [ptr, var, atr] : lst) {
      freq[ptr] = MN2();
    }
    
    occ[node] = 1;
    //cerr << "-------\n";
    for(auto [x, e] : g[node]) {
      if(occ[x] != 1)
        decomp(x);
    }
    return;
  }
  
}


signed best_path(signed n, signed k, signed H[][2], signed L[]) {
  K = k;
  for(int i = 0; i < n - 1; i++)
    g[H[i][0]].emplace_back(H[i][1], L[i]),
    g[H[i][1]].emplace_back(H[i][0], L[i]);
  Centr::lst.reserve(n);
  Centr::decomp(0);
  if(mn == nmax) return -1;
  return mn;
}

Compilation message (stderr)

race.cpp:22:6: warning: #warning idk [-Wcpp]
   22 |     #warning idk
      |      ^~~~~~~
race.cpp: In function 'void Centr::init(ll, ll)':
race.cpp:66:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |     for(auto [x, e] : g[node]) {
      |              ^
race.cpp: In function 'll Centr::findcentr(ll, ll, ll)':
race.cpp:77:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |     for(auto [x, e] : g[node]) {
      |              ^
race.cpp: In function 'void Centr::dfs(ll, ll, ll, ll, ll)':
race.cpp:92:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   92 |     for(auto [x, e] : g[node]) {
      |              ^
race.cpp: In function 'void Centr::decomp(ll)':
race.cpp:106:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  106 |     for(auto [x, e] : g[node]) {
      |              ^
race.cpp:110:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  110 |     for(auto [ptr, val, atr] : lst) {
      |              ^
race.cpp:115:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  115 |     for(auto [ptr, val, atr] : lst) {
      |              ^
race.cpp:119:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  119 |     for(auto [ptr, var, atr] : lst) {
      |              ^
race.cpp:125:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  125 |     for(auto [x, e] : g[node]) {
      |              ^

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