Submission #987707

#	Time	Username	Problem	Language	Result	Execution time	Memory
987707		Tsagana	Race (IOI11_race)	C++14	100 / 100	434 ms	90076 KiB

race

#include "race.h"

#include<bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define F first
#define S second

using namespace std;

int d, dsu[200001], cc[200001], lz[200001][2], z, inf=2e9;
bitset<200001> vtd;
vector  <pair<int, int>> adj[200001];
multiset<pair<int, int>>  ms[200001];
 
int fd(int x) {
  if (dsu[x] == x) return x;
  return dsu[x] = fd(dsu[x]);
}
 
void jo(int x,int y) {
  int k, w; x = fd(x); y = fd(y);
  if (cc[x] < cc[y]) swap(x, y);
  
  for (auto it: ms[y]) {
    k = it.F + lz[y][1];
    w = it.S + lz[y][0];
    auto it2 = ms[x].lb({d - k - lz[x][1], -inf});  
    if (it2 != ms[x].end() && it2->F + lz[x][1] == d - k)
    z = min(z, w + it2->S + lz[x][0]);
  }
  for (auto it: ms[y]) {
    k = it.F + lz[y][1];
    w = it.S + lz[y][0];
    ms[x].insert({k - lz[x][1], w - lz[x][0]});
  }
  dsu[y] = x; cc[x] += cc[y];
}
 
void dfs(int x) {
  vtd[x] = cc[x] = 1; dsu[x] = x;
  ms[x].insert({0, 0});
  for (auto i: adj[x]) {
    int l = i.F, w = i.S;
    if (!vtd[l]) {
      dfs(l);
      lz[fd(l)][0]++;
      lz[fd(l)][1] += w;
      jo(x,l);
    }
  }
}
 
int best_path(int n,int od,int ed[][2],int wg[]) {
  int k, l;
  d = od;
  for (int i = 0; i < n-1; i++) {
    k = ed[i][0];
    l = ed[i][1];
    adj[k].pb({l, wg[i]});
    adj[l].pb({k, wg[i]});
  }
  z = inf;
  dfs(0);
  if (z == inf) z = -1;
  return z;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int)':
race.cpp:46:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   46 |   vtd[x] = cc[x] = 1; dsu[x] = x;
      |            ~~~~~~^~~

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