제출 #415636

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
415636		amoo_safar	Robot (JOI21_ho_t4)	C++17	100 / 100	2901 ms	155044 KiB

Main

// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<int, int> pii;

const ll Mod = 1000000007LL;
const int N = 4e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

int to[N], c[N], p[N], m = 2;
vector<int> G[N];

ll dis[3][N]; // 0 -> Null, 1 -> fixed

ll sm[N], cost[N];

int nl[N], cn[N];

map<int, int> mp[N];

map<int, vector<int>> g[N];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, _m;
	cin >> n >> _m;
	int u, v;
	for(int i = 0; i < _m; i++){
		cin >> u >> v >> c[m] >> p[m];
		
		c[m + 1] = c[m]; p[m + 1] = p[m];
		to[m] = v; to[m + 1] = u;
		
		G[u].pb(m);
		G[v].pb(m + 1);
		g[u][c[m]].pb(m);
		g[v][c[m]].pb(m + 1);

		m += 2;
	}
	to[0] = 1;
	to[1] = -1;
	c[0] = c[1] = _m + 2;


	for(int i = 1; i <= n; i++){
		for(auto e : G[i]){
			sm[c[e]] += p[e];
		}
		for(auto e : G[i]){
			cost[e] = sm[c[e]] - p[e];
		}
		for(auto e : G[i]){
			sm[c[e]] -= p[e];
		}
	}

	memset(dis, 31, sizeof dis);

	dis[0][0] = 0;
	set< pair<ll, pii> > st;
	st.insert({0, {0, 0}});
	ll ans = Inf;
	
	// memset(la, -1, sizeof la);

	while(!st.empty()){
		pii fr = st.begin() -> S;
		st.erase(st.begin());
		ll d = dis[fr.F][fr.S];
		int ed = fr.S;
		u = to[fr.S];
		
		if(fr.F == 0){
			// mp[u][c[ed]] ++;
			// if(mp[u][c[ed]] > N) continue;
			// 	mp[u][c[ed]] ++;
			// } else {

			// }
			nl[u] ++;
			if(nl[u] > 2) continue;
		} else if (fr.F == 1){
			cn[u] ++;
			if(cn[u] > 2) continue;
			// cn[u] ++;
			// if(cn[u] > 2) continue;
			// if(la[u] == c[ed]) continue;
			// la[u] = c[ed];
			// cn[u] ++;
			// if(cn[u] > 2) continue;
		} else {
			mp[u][c[ed]] ++;
			if(mp[u][c[ed]] > 2)
				continue;
		}
		// cerr << "## " << d << ' ' << ed << ' ' << u << '\n';

		for(auto nx : (fr.F == 2 ? g[u][c[ed]] : G[u] ) ){
			if((nx ^ 1) == ed) continue;
			// cerr << "! " << ' ' << nx << '\n';
			for(int ch = 0; ch < 3; ch ++){

				if(fr.F == 2 && ch != 1)
					continue;
				if(fr.F == 2 && c[ed] != c[nx])
					continue;
				
				ll cst = cost[nx];
				if(ch == 0) cst = p[nx];
				// if(ch == 1 && c[ed] == c[nx] && fr.F == 0)
				// 	cst -= p[ed];
				if(ch == 2)
					cst = 0;

				// cerr << "^ " << dis[c]
				if(dis[ch][nx] > d + cst){
					// st.erase({dis[ch][nx], {ch, nx}});
					dis[ch][nx] = d + cst;
					st.insert({dis[ch][nx], {ch, nx}});
				}
			}
		}
		if(u == n && fr.F != 2)
			ans = min(ans, d);
		
	}
	cout << (ans == Inf ? -1 : ans) << '\n';
	return 0;
}

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