Submission #886893

#	Time	Username	Problem	Language	Result	Execution time	Memory
886893		Zero_OP	Race (IOI11_race)	C++14	100 / 100	582 ms	41436 KiB

race

#include<bits/stdc++.h>

using namespace std;

#define range(v) begin(v), end(v)
#define compact(v) v.erase(unique(range(v)), end(v))

template<class T> bool minimize(T& a, T b){
  if(a > b) return a = b, true;
  return false;
}

template<class T> bool maximize(T& a, T b){
  if(a < b) return a = b, true;
  return false;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int N = 2e5 + 5;
const int inf = 1e9;

int n, k, ans = inf, sz[N];
bool del[N];
vector<pair<int, int>> g[N];

int dfsSize(int u, int e){
  sz[u] = 1;
  for(auto [v, w] : g[u]) if(v != e and !del[v]){
    sz[u] += dfsSize(v, u);
  }
  return sz[u];
}

int getCentroid(int u, int e, int target){
  for(auto [v, w] : g[u]) if(v != e and !del[v] and sz[v] * 2 > target){
    return getCentroid(v, u, target);
  }
  return u;
}

map<int, int> cnt;
stack<pair<int, int>> op;
void init(){
  cnt.clear();
}

void add(int w, int l){
  if(cnt.find(w) == cnt.end()) cnt[w] = l;
  else minimize(cnt[w], l);
}

int query(int target){
  if(target == 0) return 0;
  if(cnt.find(target) == cnt.end()) return inf;
  return cnt[target];
}

void dfs(int u, int e, int sumW, int sumL){
  if(sumW > k) return;
  op.push({sumW, sumL});
  minimize(ans, query(k - sumW) + sumL);

  for(auto [v, w] : g[u]) if(v != e and !del[v]){
    dfs(v, u, sumW + w, sumL + 1);
  }
}

void decompose(int u, int e){
  int c = getCentroid(u, e, dfsSize(u, e));
  del[c] = true;
  init();
  for(auto [v, w] : g[c]) if(!del[v]){
    dfs(v, c, w, 1);
    while(!op.empty()){
      add(op.top().first, op.top().second);
      op.pop();
    }
  }

  for(auto [v, w] : g[c]) if(!del[v]){
    decompose(v, c);
  }
}

int best_path(int N, int K, int H[][2], int L[]){
  n = N, k = K;
  for(int i = 0; i + 1 < n; ++i){
    int u = H[i][0], v = H[i][1], w = L[i];
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }
  decompose(0, 0);
  return (ans == inf ? -1 : ans);
}

//void Zero_OP(){
//  cin >> n >> k;
//  for(int i = 1; i < n; ++i){
//    int u, v, w;
//    cin >> u >> v >> w;
//    g[u].push_back({v, w});
//    g[v].push_back({u, w});
//  }
//
//  decompose(0, 0);
//  cout << (ans == inf ? -1 : ans) << '\n';
//}
//
//int main(){
//  ios_base::sync_with_stdio(0);
//  cin.tie(0);
//
//  #define task "antuvu"
//  if(fopen(task".inp", "r")){
//    freopen(task".inp", "r", stdin);
//    freopen(task".out", "w", stdout);
//  }
//
//  Zero_OP();
//
//  return 0;
//}

Compilation message (stderr)

race.cpp: In function 'int dfsSize(int, int)':
race.cpp:31:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |   for(auto [v, w] : g[u]) if(v != e and !del[v]){
      |            ^
race.cpp: In function 'int getCentroid(int, int, int)':
race.cpp:38:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |   for(auto [v, w] : g[u]) if(v != e and !del[v] and sz[v] * 2 > target){
      |            ^
race.cpp: In function 'void dfs(int, int, int, int)':
race.cpp:66:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |   for(auto [v, w] : g[u]) if(v != e and !del[v]){
      |            ^
race.cpp: In function 'void decompose(int, int)':
race.cpp:75:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |   for(auto [v, w] : g[c]) if(!del[v]){
      |            ^
race.cpp:83:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |   for(auto [v, w] : g[c]) if(!del[v]){
      |            ^

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