oj.uz

Submission #415624

# Submission time Handle Problem Language Result Execution time Memory
415624 2021-06-01T09:52:08 Z amoo_safar Robot (JOI21_ho_t4) C++17
34 / 100
 3000 ms 84780 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];

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);

		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 {

		}
		// cerr << "## " << d << ' ' << ed << ' ' << u << '\n';
		for(auto nx : 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.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 37836 KB Output is correct
2 Correct 20 ms 37936 KB Output is correct
3 Correct 23 ms 37836 KB Output is correct
4 Correct 23 ms 37836 KB Output is correct
5 Correct 23 ms 37900 KB Output is correct
6 Correct 22 ms 37836 KB Output is correct
7 Correct 24 ms 38176 KB Output is correct
8 Correct 20 ms 37964 KB Output is correct
9 Correct 36 ms 38356 KB Output is correct
10 Correct 35 ms 38356 KB Output is correct
11 Correct 41 ms 38408 KB Output is correct
12 Correct 27 ms 38288 KB Output is correct
13 Correct 35 ms 38476 KB Output is correct
14 Correct 36 ms 38476 KB Output is correct
15 Correct 21 ms 37964 KB Output is correct
16 Correct 26 ms 38052 KB Output is correct
17 Correct 22 ms 38120 KB Output is correct
18 Correct 25 ms 37984 KB Output is correct
19 Correct 27 ms 38304 KB Output is correct
20 Correct 29 ms 37964 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 775 ms 62228 KB Output is correct
2 Correct 218 ms 46352 KB Output is correct
3 Correct 1348 ms 84780 KB Output is correct
4 Correct 517 ms 50556 KB Output is correct
5 Execution timed out 3060 ms 67256 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 37836 KB Output is correct
2 Correct 20 ms 37936 KB Output is correct
3 Correct 23 ms 37836 KB Output is correct
4 Correct 23 ms 37836 KB Output is correct
5 Correct 23 ms 37900 KB Output is correct
6 Correct 22 ms 37836 KB Output is correct
7 Correct 24 ms 38176 KB Output is correct
8 Correct 20 ms 37964 KB Output is correct
9 Correct 36 ms 38356 KB Output is correct
10 Correct 35 ms 38356 KB Output is correct
11 Correct 41 ms 38408 KB Output is correct
12 Correct 27 ms 38288 KB Output is correct
13 Correct 35 ms 38476 KB Output is correct
14 Correct 36 ms 38476 KB Output is correct
15 Correct 21 ms 37964 KB Output is correct
16 Correct 26 ms 38052 KB Output is correct
17 Correct 22 ms 38120 KB Output is correct
18 Correct 25 ms 37984 KB Output is correct
19 Correct 27 ms 38304 KB Output is correct
20 Correct 29 ms 37964 KB Output is correct
21 Correct 775 ms 62228 KB Output is correct
22 Correct 218 ms 46352 KB Output is correct
23 Correct 1348 ms 84780 KB Output is correct
24 Correct 517 ms 50556 KB Output is correct
25 Execution timed out 3060 ms 67256 KB Time limit exceeded
26 Halted 0 ms 0 KB -