Submission #532062

#	Time	Username	Problem	Language	Result	Execution time	Memory
532062		amunduzbaev	Robot (JOI21_ho_t4)	C++17	34 / 100	277 ms	51184 KiB

Main

#include "bits/stdc++.h"
using namespace std;

#define ar array
#define int long long

const int N = 1e5 + 5;
struct node{
	int a, b, c, p;
};
map<int, vector<ar<int, 2>>> edges[N], ee[N];
map<int, int> ss[N], uu[N];
int d[N], used[N];
node e[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	for(int i=0;i<m;i++){
		node& x = e[i]; cin>>x.a>>x.b>>x.c>>x.p;
		edges[x.a][x.c].push_back({x.b, x.p});
		edges[x.b][x.c].push_back({x.a, x.p});
		ee[x.a][x.c].push_back({x.b, x.p});
		ee[x.b][x.c].push_back({x.a, x.p});
		ss[x.a][x.c] += x.p;
		ss[x.b][x.c] += x.p;
	}
	
	priority_queue<ar<int, 4>, vector<ar<int, 4>>, greater<ar<int, 4>>> q;
	q.push({0, 1, 0, 0});
	memset(d, 127, sizeof d);
	while(!q.empty()){
		int D = q.top()[0], u = q.top()[1], v = q.top()[2], c = q.top()[3]; q.pop();
		//~ cout<<D<<" "<<u<<" "<<v<<" "<<c<<endl;
		if(c < 0){ 
			c = abs(c);
			auto& t = ee[u][c];
			int& sum = ss[u][c];
			ar<int, 2> p {};
			for(auto x : t){
				if(x[0] == v) { p = x; continue; }
				if(used[x[0]]) continue;
				q.push({D + sum - x[1], x[0], u, c});
			}
			t.clear();
			if(p[0]) t.push_back(p);
		} else if(!used[u]) {
			used[u] = 1;
			d[u] = D;
			for(auto [c, v] : edges[u]){
				int& sum = ss[u][c];
				for(auto x : v){
					if(used[x[0]]) continue;
					q.push({D, x[0], u, -c});
					if(sum == x[1]){
						q.push({D, x[0], u, c});
					} else {
						q.push({D + min(sum - x[1], x[1]), x[0], u, c});
					}
				}
			}
		}
	}
	
	if(d[n] > 1e18) cout<<-1<<"\n";
	else cout<<d[n]<<"\n";
}

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