Submission #1282670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282670		kaiboy	Robot (JOI21_ho_t4)	C++20	0 / 100	64 ms	22136 KiB

Main

#include <algorithm>
#include <iostream>

using namespace std;

const       int   N = 100000;
const       int   M = 200000;
const       int  N_ = (M << 1) + N;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;

int ij[M], cc[M], ww[M];
int *eh[N], eo[N];
int *ej_[N_], eo_[N_];
long long *ew_[N_], dd[N_];
int pq[N_], iq[N_ + 1], pq_cnt;

void append(int i, int h) {
	int o = eo[i]++;
	if (!o)
		eh[i] = (int *) malloc(sizeof *eh[i]);
	else if (!(o & o - 1))
		eh[i] = (int *) realloc(eh[i], (o << 1) * sizeof *eh[i]);
	eh[i][o] = h;
}

void append_(int i, int j, long long w) {
	int o = eo_[i]++;
	if (!o) {
		ej_[i] = (int *) malloc(sizeof *ej_[i]);
		ew_[i] = (long long *) malloc(sizeof *ew_[i]);
	} else if (!(o & o - 1)) {
		ej_[i] = (int *) realloc(ej_[i], (o << 1) * sizeof *ej_[i]);
		ew_[i] = (long long *) realloc(ew_[i], (o << 1) * sizeof *ew_[i]);
	}
	ej_[i][o] = j;
	ew_[i][o] = w;
}

bool lt(int i, int j) {
	return dd[i] < dd[j];
}

int p2(int p) {
	return (p <<= 1) > pq_cnt ? 0 : p ^ (p < pq_cnt && lt(iq[p ^ 1], iq[p]));
}

void pq_up(int i) {
	int j, p, q;
	for (p = pq[i]; (q = p >> 1) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_dn(int i) {
	int j, p, q;
	for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_add_last(int i) {
	iq[pq[i] = ++pq_cnt] = i;
}

int pq_remove_first() {
	int i = iq[1], j = iq[pq_cnt--];
	if (i != j)
		pq[j] = 1, pq_dn(j);
	pq[i] = 0;
	return i;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, m; cin >> n >> m;
	for (int h = 0; h < m; h++) {
		int i, j, c, w; cin >> i >> j >> c >> w, i--, j--, c--;
		ij[h] = i ^ j, cc[h] = c, ww[h] = w;
		append(i, h << 1 ^ 0);
		append(j, h << 1 ^ 1);
	}
	for (int i = 0; i < n; i++)
		sort(eh[i], eh[i] + eo[i], [] (int h0, int h1) { return cc[h0 >> 1] < cc[h1 >> 1]; });
	int n_ = (m <<= 1) + n;
	for (int i = 0; i < n; i++) {
		for (int o = 0; o < eo[i]; o++) {
			int h = eh[i][o], c = cc[h >> 1], w = ww[h >> 1];
			append_(h, m + i, 0);
			append_(m + i, h ^ 1,
					(!o || c > cc[eh[i][o - 1] >> 1]) &&
					(o + 1 == eo[i] || c < cc[eh[i][o + 1] >> 1])
					? 0 : w);
		}
		for (int o = 0, o_ = 0; o < eo[i]; ) {
			int c = cc[eh[i][o] >> 1];
			int w0 = 0, h0 = -1;
			int w1 = 0, h1 = -1;
			long long s = 0;
			for (int h; o_ < eo[i] && cc[(h = eh[i][o_]) >> 1] == c; o_++) {
				int w = ww[h >> 1];
				if (w0 < w) {
					w1 = w0, h1 = h0;
					w0 = w, h0 = h;
				} else if (w1 < w)
					w1 = w, h1 = h;
				s += w;
			}
			if (w1)
				for ( ; o < o_; o++) {
					int h = eh[i][o], w = ww[h >> 1];
					if (h != h0)
						append_(h, h0 ^ 1, s - w - w0);
					else
						append_(h, h1 ^ 1, s - w - w1);
				}
			else
				o = o_;
		}
	}
	for (int i = 0; i < n_; i++)
		dd[i] = INF;
	dd[m] = 0, pq_add_last(m);
	while (pq_cnt) {
		int i = pq_remove_first();
		long long d = dd[i];
		if (i == n_ - 1) {
			cout << d << '\n';
			return 0;
		}
		for (int o = 0; o < eo_[i]; o++) {
			int j = ej_[i][o]; long long w = ew_[i][o];
			long long e = dd[i] + w;
			if (dd[j] > e) {
				if (dd[j] == INF)
					pq_add_last(j);
				dd[j] = e, pq_up(j);
			}
		}
	}
	cout << "-1\n";
	return 0;
}

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42