Submission #1025980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025980		MinaRagy06	Dungeons Game (IOI21_dungeons)	C++17	Compilation error	0 ms	0 KiB

dungeons

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#pragma GCC optimize("Ofast")

int n;
const int N = 400'005;
const int LOG = 25, B = 8, LIFTS = 7; //LIFTS = log_B(1e7 + N)
const ll inf = 1e18;
struct node {
	int anc;
	ll strength, bound;
	node() {}
	node(int _anc, ll _strength, ll _bound) {
		anc = _anc;
		strength = _strength;
		bound = _bound;
	}
	void operator+=(const node &r) {
		//i -> l -> r
		anc = r.anc;
		bound = min(bound, r.bound - strength);
		strength += r.strength;
	}
};
vector<int> s, p, w, l;
node lift[N][LOG][LIFTS];
const int M = 1 << LOG;
int logs[M];
void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
	logs[1] = 0;
	for (int i = 2; i < M; i++) {
		logs[i] = logs[i >> 1] + 1;
	}
	n = _n, s = _s, p = _p, w = _w, l = _l;
	s.push_back(0), p.push_back(0), w.push_back(n), l.push_back(n);
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j < LOG; j++) {
			if (s[i] < (1 << j)) {
				lift[i][j][0] = node(w[i], s[i], inf);
			} else if (s[i] >= (1 << (j + 1))) {
				lift[i][j][0] = node(l[i], p[i], inf);
			} else { //log(s[i]) == log(z)
				lift[i][j][0] = node(l[i], p[i], s[i] - 1);
			}
		}
	}
	for (int k = 1; k < LIFTS; k++) {
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j < LOG; j++) {
				lift[i][j][k] = lift[i][j][k - 1];
				for (int o = 1; o < B; o++) {
					lift[i][j][k] += lift[lift[i][j][k].anc][j][k - 1];
				}
			}
		}
	}
}
ll simulate(int x, int _z) {
	ll z = _z;
	while (x != n) {
		if (z >= s[x]) {
			z += s[x];
			x = w[x];
		} else{
			z += p[x];
			x = l[x];
		}
		int lg = (z < M? logs[z] : LOG - 1);
		for (int k = LIFTS - 1; k >= 0; k--) {
			for (int o = 1; o < B; o++) {
				ll newz = z + lift[x][lg][k].strength;
				if (z <= lift[x][lg][k].bound && (z >= (1 << (LOG - 1)) || (newz < M && logs[newz] == lg))) {
					z += lift[x][lg][k].strength;
					x = lift[x][lg][k].anc;
				}
			}
		}
	}
	return z;
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	ll st = chrono::steady_clock::now().time_since_epoch().count();
	int _n;
	cin >> _n;
	vector<int> _s(_n), _p(_n), _w(_n), _l(_n);
	for (int i = 0; i < _n; i++) cin >> _s[i];
	for (int i = 0; i < _n; i++) cin >> _p[i];
	for (int i = 0; i < _n; i++) cin >> _w[i];
	for (int i = 0; i < _n; i++) cin >> _l[i];
	init(_n, _s, _p, _w, _l);
	int q;
	cin >> q;
	while (q--) {
		int x, z;
		cin >> x >> z;
		cout << simulate(x, z) << '\n';
	}
	ll en = chrono::steady_clock::now().time_since_epoch().count();
//	cout << (en - st) / 1e9 << "s\n";
	return 0;
}

Compilation message (stderr)

dungeons.cpp: In function 'int main()':
dungeons.cpp:84:5: warning: unused variable 'st' [-Wunused-variable]
   84 |  ll st = chrono::steady_clock::now().time_since_epoch().count();
      |     ^~
dungeons.cpp:100:5: warning: unused variable 'en' [-Wunused-variable]
  100 |  ll en = chrono::steady_clock::now().time_since_epoch().count();
      |     ^~
/usr/bin/ld: /tmp/ccq1Qakc.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccOdN8Ob.o:dungeons.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status