Submission #1122338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122338		vjudge1	Robot (JOI21_ho_t4)	C++17	100 / 100	961 ms	151312 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 + 6 * m;
    vector <vector <pair <int, int> > > g(sz);
    vector <int> a(m), b(m), color(m), price(m);
    for (int i = 0; i < m; ++i) {
    	int u, v;
    	cin >> u >> v >> color[i] >> price[i];
    	color[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) {
    	g[u].app({v,c});
    };
    vector <vector <int> > who(m);

    int ptr = n + 4 * 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), price[i]);
    		who[color[i]].app(i);
    		cs.app(color[i]);
    	}
    	for (int col : cs) {
    		if (!who[col].empty()) {
    			int sum = 0;
    			for (int i : who[col]) {
    				sum += price[i];
    			}
    			for (int i : who[col]) {
    				edge(u, num(i, u, 0), sum - price[i]);
    			}

    			if (who[col].size() > 1) {
    				int f = who[col].front();
    				for (int i : who[col]) {
    					if (price[i] > price[f]) {
    						f = i;
    					}
    				}
    				for (int e : who[col]) {
    					if (e != f) {
    						edge(num(e, a[e]^b[e]^u, 1), num(f, u, 0), 
    							sum - price[e] - price[f]);

    						edge(num(f, a[f]^b[f]^u, 1), num(e, u, 0),
    							sum - price[e] - price[f]);
    					}
    				}
    				int uu = ptr++;
	    			for (int e : who[col]) {
	    				if (e != f) {
		    				edge(num(e, a[e]^b[e]^u, 1), uu, price[f] - price[e]);
		    				edge(uu, num(e, u, 0), sum - price[f] - price[e]);
	    				}
	    			}
    			}

	    		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: 34 / 34
• Subtask 2: 24 / 24
• Subtask 3: 42 / 42