Submission #233093

#	Time	Username	Problem	Language	Result	Execution time	Memory
233093		islingr	Roller Coaster Railroad (IOI16_railroad)	C++14	Compilation error	0 ms	0 KiB

railroad

#include <algorithm>
#include <vector>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define trav(x, v) for (auto &x : v)
#define all(x) begin(x), end(x)
#define lb(x...) lower_bound(x)
#define sz(x) int((x).size())
#define eb(x...) emplace_back(x)

vi nxt, rnk;
int head(int u) { return nxt[u] != -1 ? nxt[u] = head(nxt[u]) : u; }
bool unite(int u, int v) {
	u = head(u); v = head(v);
	if (u == v) return false;
	if (rnk[u] > rnk[v]) nxt[v] = u;
	else {
		nxt[u] = v;
		if (rnk[u] == rnk[v]) ++rnk[v];
	}
	return true;
}

const int inf = 2e9;
using ll = int64_t;
using vi = vector<int>;

ll plan_roller_coaster(vi s, vi t) {
	ll ans = 0;
	
	s.eb(inf); t.eb(1); int n = sz(s);

	vi p = s; p.insert(end(p), all(t));
	sort(all(p)); p.erase(unique(all(p)), end(p));	
	int m = sz(p); nxt.resize(m, -1); rnk.resize(m, 0);

	vi sum(m--), e;
	rep(i, 0, n) {
		int l = lb(all(p), s[i]) - begin(p), r = lb(all(p), t[i]) - begin(p);
		unite(l, r);
		++sum[l]; --sum[r];
	}
	rep(i, 0, m) sum[i + 1] += sum[i];

	rep(i, 0, m) {
		if (sum[i]) {
			unite(i + 1, i);
			if (sum[i] > 0) ans += 1ll * sum[i] * (p[i + 1] - p[i]);
		} else e.eb(i);
	}

	sort(all(e), [&p](int u, int v){ return p[u + 1] - p[u] < p[v + 1] - p[v]; });
	trav(u, e) if (unite(u, u + 1)) ans += p[u + 1] - p[u];

	return ans;
}

Compilation message (stderr)

railroad.cpp:12:1: error: 'vi' does not name a type
 vi nxt, rnk;
 ^~
railroad.cpp: In function 'int head(int)':
railroad.cpp:13:26: error: 'nxt' was not declared in this scope
 int head(int u) { return nxt[u] != -1 ? nxt[u] = head(nxt[u]) : u; }
                          ^~~
railroad.cpp:13:26: note: suggested alternative: 'exit'
 int head(int u) { return nxt[u] != -1 ? nxt[u] = head(nxt[u]) : u; }
                          ^~~
                          exit
railroad.cpp: In function 'bool unite(int, int)':
railroad.cpp:17:6: error: 'rnk' was not declared in this scope
  if (rnk[u] > rnk[v]) nxt[v] = u;
      ^~~
railroad.cpp:17:6: note: suggested alternative: 'rand'
  if (rnk[u] > rnk[v]) nxt[v] = u;
      ^~~
      rand
railroad.cpp:17:23: error: 'nxt' was not declared in this scope
  if (rnk[u] > rnk[v]) nxt[v] = u;
                       ^~~
railroad.cpp:17:23: note: suggested alternative: 'exit'
  if (rnk[u] > rnk[v]) nxt[v] = u;
                       ^~~
                       exit
railroad.cpp:19:3: error: 'nxt' was not declared in this scope
   nxt[u] = v;
   ^~~
railroad.cpp:19:3: note: suggested alternative: 'exit'
   nxt[u] = v;
   ^~~
   exit
railroad.cpp: In function 'll plan_roller_coaster(vi, vi)':
railroad.cpp:36:17: error: 'nxt' was not declared in this scope
  int m = sz(p); nxt.resize(m, -1); rnk.resize(m, 0);
                 ^~~
railroad.cpp:36:17: note: suggested alternative: 'exit'
  int m = sz(p); nxt.resize(m, -1); rnk.resize(m, 0);
                 ^~~
                 exit
railroad.cpp:36:36: error: 'rnk' was not declared in this scope
  int m = sz(p); nxt.resize(m, -1); rnk.resize(m, 0);
                                    ^~~