oj.uz

Submission #415572

# Submission time Handle Problem Language Result Execution time Memory
415572 2021-06-01T08:47:01 Z amoo_safar Robot (JOI21_ho_t4) C++17
34 / 100
 3000 ms 91184 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[2][N]; // 0 -> Null, 1 -> fixed

ll sm[N], cost[N];

int nl[N];
int la[N], cn[N];


map<int, int> mp0[N], mp1[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){
			// nl[u] ++;
			// if(nl[u] > 2) continue;
		} else {
			// if(mp1[u].count(c[ed])){
			// 	if(mp1[u][c[ed]] == 2) continue;
			// 	mp1[u][c[ed]] ++;
			// } else {

			// }
			cn[u] ++;
			if(cn[u] > 2) continue;
			// if(la[u] == c[ed]) continue;
			// la[u] = c[ed];
			// cn[u] ++;
			// if(cn[u] > 2) continue;
		}
		// cerr << "## " << d << ' ' << ed << ' ' << u << '\n';
		for(auto nx : G[u]){
			if((nx ^ 1) == ed) continue;
			// cerr << "! " << ' ' << nx << '\n';
			for(int ch = 0; ch < 2; ch ++){
				ll cst = cost[nx];
				if(ch == 0) cst = p[nx];
				if(ch == 1 && c[ed] == c[nx] && fr.F == 0)
					cst -= p[ed];
				// 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) 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 36 ms 55152 KB Output is correct
2 Correct 35 ms 55136 KB Output is correct
3 Correct 39 ms 55140 KB Output is correct
4 Correct 41 ms 55152 KB Output is correct
5 Correct 34 ms 55116 KB Output is correct
6 Correct 45 ms 55080 KB Output is correct
7 Correct 43 ms 55268 KB Output is correct
8 Correct 42 ms 55244 KB Output is correct
9 Correct 53 ms 55444 KB Output is correct
10 Correct 53 ms 55392 KB Output is correct
11 Correct 59 ms 55592 KB Output is correct
12 Correct 43 ms 55368 KB Output is correct
13 Correct 50 ms 55492 KB Output is correct
14 Correct 58 ms 55568 KB Output is correct
15 Correct 40 ms 55212 KB Output is correct
16 Correct 44 ms 55252 KB Output is correct
17 Correct 40 ms 55372 KB Output is correct
18 Correct 46 ms 55116 KB Output is correct
19 Correct 41 ms 55476 KB Output is correct
20 Correct 44 ms 55124 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 603 ms 72952 KB Output is correct
2 Correct 188 ms 62236 KB Output is correct
3 Correct 1416 ms 91184 KB Output is correct
4 Correct 340 ms 65676 KB Output is correct
5 Execution timed out 3066 ms 90684 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 55152 KB Output is correct
2 Correct 35 ms 55136 KB Output is correct
3 Correct 39 ms 55140 KB Output is correct
4 Correct 41 ms 55152 KB Output is correct
5 Correct 34 ms 55116 KB Output is correct
6 Correct 45 ms 55080 KB Output is correct
7 Correct 43 ms 55268 KB Output is correct
8 Correct 42 ms 55244 KB Output is correct
9 Correct 53 ms 55444 KB Output is correct
10 Correct 53 ms 55392 KB Output is correct
11 Correct 59 ms 55592 KB Output is correct
12 Correct 43 ms 55368 KB Output is correct
13 Correct 50 ms 55492 KB Output is correct
14 Correct 58 ms 55568 KB Output is correct
15 Correct 40 ms 55212 KB Output is correct
16 Correct 44 ms 55252 KB Output is correct
17 Correct 40 ms 55372 KB Output is correct
18 Correct 46 ms 55116 KB Output is correct
19 Correct 41 ms 55476 KB Output is correct
20 Correct 44 ms 55124 KB Output is correct
21 Correct 603 ms 72952 KB Output is correct
22 Correct 188 ms 62236 KB Output is correct
23 Correct 1416 ms 91184 KB Output is correct
24 Correct 340 ms 65676 KB Output is correct
25 Execution timed out 3066 ms 90684 KB Time limit exceeded
26 Halted 0 ms 0 KB -