Submission #987702

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
987702	2024-05-23T11:39:08 Z	Tsagana	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KB

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[200069], cc[200069], lz[200069][2], z, inf=1e18;
vector  <pair<int, int>> adj[200069];
multiset<pair<int, int>>  ms[200069];
 
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

race.cpp:16:55: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   16 | int d, dsu[200069], cc[200069], lz[200069][2], z, inf=1e18;
      |                                                       ^~~~
race.cpp: In function 'void jo(int, int)':
race.cpp:11:11: error: 'struct std::_Rb_tree_const_iterator<std::pair<int, int> >' has no member named 'first'
   11 | #define F first
      |           ^~~~~
race.cpp:33:35: note: in expansion of macro 'F'
   33 |     if (it2 != ms[x].end() && it2.F + lz[x][1] == d - k)
      |                                   ^
race.cpp:12:11: error: 'struct std::_Rb_tree_const_iterator<std::pair<int, int> >' has no member named 'second'
   12 | #define S second
      |           ^~~~~~
race.cpp:34:24: note: in expansion of macro 'S'
   34 |     z = min(z, w + it2.S + lz[x][0]);
      |                        ^
race.cpp: In function 'void dfs(int)':
race.cpp:45:3: error: 'vtd' was not declared in this scope; did you mean 'std'?
   45 |   vtd[x] = cc[x] = 1; dsu[x] = x;
      |   ^~~
      |   std