Submission #529575

#	Time	Username	Problem	Language	Result	Execution time	Memory
529575		abc864197532	Robot (JOI21_ho_t4)	C++17	0 / 100	3059 ms	20000 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T i, U ...j) {
	cout << i << ' ', abc(j...);
}
template <typename T> void printv(T l, T r) {
	for (; l != r; ++l) cout << *l << " \n"[l + 1 == r];
}
#ifdef Doludu
#define test(x...) abc("[" + string(#x) + "]", x)
#define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#else
#define test(x...) void(0)
#define owo ios::sync_with_stdio(false), cin.tie(0)
#endif
const int N = 100000;

struct edge {
	int v, c, p;
};

vector <edge> adj[N];
map <int, int> col_num[N];

int main () {
	owo;
	int n, m;
	cin >> n >> m;
	for (int i = 0, u, v, c, p; i < m; ++i) {
		cin >> u >> v >> c >> p, --u, --v, --c;
		adj[u].pb({v, c, p});
		adj[v].pb({u, c, p});
		col_num[u][c]++, col_num[v][c]++;
	}
	map <pair <pii, int>, int> dis;
	dis[mp(mp(0, 0), -1)] = 0;
	priority_queue <pair <int, pair <pii, int>>> pq;
	pq.emplace(0, mp(mp(0, -1), 0));
	while (!pq.empty()) {
		int d, v, c, del; d = pq.top().X, tie(v, c) = pq.top().Y.X, del = pq.top().Y.Y; pq.pop();
		if (d > dis[mp(mp(v, c), del)])
			continue;
		if (del)
			col_num[v][c]--;
		for (edge &e : adj[v]) {
			if (col_num[v][e.c] == 1) {
				// no change
				if (!dis.count(mp(mp(e.v, e.c), 0)) || dis[mp(mp(e.v, e.c), 0)] > d) {
					dis[mp(mp(e.v, e.c), 0)] = d;
					pq.emplace(d, mp(mp(e.v, e.c), 0));
				}
			}
			// change
			if (!dis.count(mp(mp(e.v, e.c), 1)) || dis[mp(mp(e.v, e.c), 1)] > d + 1) {
				dis[mp(mp(e.v, e.c), 1)] = d + 1;
				pq.emplace(d + 1, mp(mp(e.v, e.c), 1));
			}
		}
		if (del)
			col_num[v][c]++;
	}
	int ans = 1 << 30;
	for (auto A : dis) if (A.X.X.X == n - 1) {
		ans = min(ans, A.Y);
	}
	if (ans == 1 << 30)
		ans = -1;
	cout << ans << endl;
}

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