Submission #1122248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122248		vjudge1	Robot (JOI21_ho_t4)	C++17	24 / 100	607 ms	110232 KiB

Main

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <fstream>
#include <array>
#include <functional>
#include <stack>
#include <memory>
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif

using namespace std;

#define int long long
#define app push_back
#define all(x) x.begin(), x.end()
#ifdef LOCAL
#define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl; }(#__VA_ARGS__, ":", __VA_ARGS__)
#define debugv(v) do { cout << #v << ": "; for (auto x : v) cout << x << ' '; cout << endl; } while(0)
#else
#define debug(...)
#define debugv(v)
#endif

int32_t main() {
    cin.tie(0);ios_base::sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector <vector <int> > e(n);
    int sz = n + 4 * m;
    vector <vector <pair <int, int> > > g(sz);
    vector <int> a(m), b(m), c(m), p(m);
    for (int i = 0; i < m; ++i) {
    	int u, v;
    	cin >> u >> v >> c[i] >> p[i];
    	c[i]--;
    	u--; v--;
    	a[i] = u;
    	b[i] = v;
    	e[u].app(i); 
    	e[v].app(i);
    }
    auto num = [&] (int i, int from, int change) {
    	return n + m * (2 * (from == a[i]) + change) + i;
    };
    auto edge = [&] (int u, int v, int c) {
    	//debug(u,v,c);
    	g[u].app({v,c});
    };
    vector <vector <int> > who(m);
    for (int u = 0; u < n; ++u) {
    	vector <int> cs;
    	for (int i : e[u]) {
    		edge(num(i, a[i]^b[i]^u, 0), u, 0);
    		edge(num(i, a[i]^b[i]^u, 1), u, 0);
    		edge(u, num(i, u, 1), p[i]);
    		who[c[i]].app(i);
    		cs.app(c[i]);
    	}
    	for (int col : cs) {
    		if (!who[col].empty()) {
    			int sum = 0;
    			for (int i : who[col]) {
    				sum += p[i];
    			}
    			for (int i : who[col]) {
    				edge(u, num(i, u, 0), sum - p[i]);
    			}
	    		if (who[col].size() == 2) {
	    			int e = who[col].front(), f = who[col].back();
	    			for (int t = 0; t < 2; ++t) {
	    				edge(num(e, a[e]^b[e]^u, 1), num(f, u, 0), 0);
	    				swap(e, f);
	    			}
	    		}
	    		who[col].clear();
    		}
    	}
    }

    const int inf = 1e18;
    vector <int> dist(sz, inf);
    dist.front() = 0;
    priority_queue <pair <int, int>, 
    vector <pair <int, int> > , greater <pair <int, int> > > q;
    q.push({0,0});
    while (!q.empty()) {
    	auto [d, u] = q.top(); q.pop();
    	if (d != dist[u]) {
    		continue;
    	}
    	debug(d,u);
    	for (auto [v, c] : g[u]) {
    		if (dist[v] > dist[u] + c) {
    			dist[v] = dist[u] + c;
    			q.push({dist[v], v});
    		}
    	}
    }
    if (dist[n - 1] == inf) {
    	cout << -1 << '\n';
    }
    else {
    	cout << dist[n - 1] << '\n';
    }

}

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