Submission #415636

# Submission time Handle Problem Language Result Execution time Memory
415636 2021-06-01T10:02:02 Z amoo_safar Robot (JOI21_ho_t4) C++17
100 / 100
2901 ms 155044 KB
// 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;
}
# Verdict Execution time Memory Grader output
1 Correct 42 ms 56652 KB Output is correct
2 Correct 41 ms 56652 KB Output is correct
3 Correct 42 ms 56652 KB Output is correct
4 Correct 35 ms 56700 KB Output is correct
5 Correct 35 ms 56772 KB Output is correct
6 Correct 41 ms 56708 KB Output is correct
7 Correct 45 ms 56944 KB Output is correct
8 Correct 37 ms 56772 KB Output is correct
9 Correct 48 ms 57540 KB Output is correct
10 Correct 43 ms 57432 KB Output is correct
11 Correct 47 ms 57412 KB Output is correct
12 Correct 44 ms 57260 KB Output is correct
13 Correct 40 ms 57444 KB Output is correct
14 Correct 39 ms 57436 KB Output is correct
15 Correct 42 ms 56900 KB Output is correct
16 Correct 44 ms 56960 KB Output is correct
17 Correct 37 ms 57132 KB Output is correct
18 Correct 35 ms 56780 KB Output is correct
19 Correct 41 ms 57180 KB Output is correct
20 Correct 45 ms 56900 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 881 ms 89776 KB Output is correct
2 Correct 329 ms 70780 KB Output is correct
3 Correct 1457 ms 109652 KB Output is correct
4 Correct 539 ms 75972 KB Output is correct
5 Correct 2836 ms 144364 KB Output is correct
6 Correct 2646 ms 133948 KB Output is correct
7 Correct 1560 ms 133504 KB Output is correct
8 Correct 989 ms 90480 KB Output is correct
9 Correct 1211 ms 90484 KB Output is correct
10 Correct 1233 ms 100496 KB Output is correct
11 Correct 239 ms 73976 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 42 ms 56652 KB Output is correct
2 Correct 41 ms 56652 KB Output is correct
3 Correct 42 ms 56652 KB Output is correct
4 Correct 35 ms 56700 KB Output is correct
5 Correct 35 ms 56772 KB Output is correct
6 Correct 41 ms 56708 KB Output is correct
7 Correct 45 ms 56944 KB Output is correct
8 Correct 37 ms 56772 KB Output is correct
9 Correct 48 ms 57540 KB Output is correct
10 Correct 43 ms 57432 KB Output is correct
11 Correct 47 ms 57412 KB Output is correct
12 Correct 44 ms 57260 KB Output is correct
13 Correct 40 ms 57444 KB Output is correct
14 Correct 39 ms 57436 KB Output is correct
15 Correct 42 ms 56900 KB Output is correct
16 Correct 44 ms 56960 KB Output is correct
17 Correct 37 ms 57132 KB Output is correct
18 Correct 35 ms 56780 KB Output is correct
19 Correct 41 ms 57180 KB Output is correct
20 Correct 45 ms 56900 KB Output is correct
21 Correct 881 ms 89776 KB Output is correct
22 Correct 329 ms 70780 KB Output is correct
23 Correct 1457 ms 109652 KB Output is correct
24 Correct 539 ms 75972 KB Output is correct
25 Correct 2836 ms 144364 KB Output is correct
26 Correct 2646 ms 133948 KB Output is correct
27 Correct 1560 ms 133504 KB Output is correct
28 Correct 989 ms 90480 KB Output is correct
29 Correct 1211 ms 90484 KB Output is correct
30 Correct 1233 ms 100496 KB Output is correct
31 Correct 239 ms 73976 KB Output is correct
32 Correct 1295 ms 106560 KB Output is correct
33 Correct 1034 ms 94048 KB Output is correct
34 Correct 1622 ms 111660 KB Output is correct
35 Correct 1448 ms 99440 KB Output is correct
36 Correct 1258 ms 105468 KB Output is correct
37 Correct 1703 ms 115380 KB Output is correct
38 Correct 1317 ms 133104 KB Output is correct
39 Correct 1276 ms 98964 KB Output is correct
40 Correct 943 ms 91764 KB Output is correct
41 Correct 1259 ms 92396 KB Output is correct
42 Correct 1781 ms 115980 KB Output is correct
43 Correct 570 ms 86816 KB Output is correct
44 Correct 2104 ms 116908 KB Output is correct
45 Correct 726 ms 87204 KB Output is correct
46 Correct 564 ms 85084 KB Output is correct
47 Correct 1073 ms 108228 KB Output is correct
48 Correct 2901 ms 155044 KB Output is correct