Submission #1265294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265294		kustov_vadim_533	Robot (JOI21_ho_t4)	C++20	0 / 100	223 ms	27856 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

#define len(v) (int)((v).size())

const int inf = 1e9;
const int sz = 1 << 20;

int tree[sz];

void init(int v, int l, int r){
	tree[v] = 0;
	if (r - l == 1) return;
	int m = (l + r) / 2;
	init(v * 2, l, m);
	init(v * 2 + 1, m, r);
}

void upd(int v, int l, int r, int qi){
	tree[v] += 1;
	if (r - l == 1){
		return;
	}
	int m = (l + r) / 2;
	if (qi < m) upd(v * 2, l, m, qi);
	else upd(v * 2 + 1, m, r, qi);
}

int sum(int v, int l, int r, int ql, int qr){
	if (l >= qr || ql >= r) return 0;
	if (l >= ql && r <= qr) return tree[v];
	int m = (l + r) / 2;
	int r1 = sum(v * 2, l, m, ql, qr);
	int r2 = sum(v * 2 + 1, m, r, ql, qr);
	return r1 + r2;
}

struct event{
	int to, cl, w;
	event(int to, int cl, int w) : to(to), cl(cl), w(w) {};
};

inline void solve(){
	int n, m;
	cin >> n >> m;

	vector<vector<event>> g(n);
	vector<map<int, int>> cnt(n);

	for (int i = 0; i < m; ++i){
		int a, b, c, p;
		cin >> a >> b >> c >> p;
		--a, --b, --c;
		cnt[a][c]++;
		cnt[b][c]++;
		g[a].emplace_back(b, c, p);
		g[b].emplace_back(a, c, p);
	}

	vector<ll> d(n, 1e18);
	d[0] = 0;

	set<pair<int, int>> q;
	q.insert({0, 0});

	while (!q.empty()){
		int v = q.begin()->second;
		q.erase(q.begin());

		for (event u : g[v]){
			int w = 0;
			if (cnt[v][u.cl] > 1){
				w = u.w;
			}

			if (d[u.to] > d[v] + w){
				if (q.find({d[u.to], u.to}) != q.end()){
					q.erase({d[u.to], u.to});
				}
				d[u.to] = d[v] + w;
				q.insert({d[u.to], u.to});
			}
		}
	}

	if (d[n - 1] >= inf){
		cout << "-1\n";
	}
	else{
		cout << d[n - 1] << '\n';
	}

}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout.precision(60);

	int t = 1;
//	cin >> t;

	while (t--) {
		solve();
	}
}

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