oj.uz

Submission #415560

# Submission time Handle Problem Language Result Execution time Memory
415560 2021-06-01T08:39:15 Z amoo_safar Robot (JOI21_ho_t4) C++17
34 / 100
 3000 ms 53436 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];

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(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 13 ms 17520 KB Output is correct
2 Correct 12 ms 17484 KB Output is correct
3 Correct 14 ms 17484 KB Output is correct
4 Correct 13 ms 17484 KB Output is correct
5 Correct 14 ms 17484 KB Output is correct
6 Correct 13 ms 17532 KB Output is correct
7 Correct 15 ms 17740 KB Output is correct
8 Correct 15 ms 17612 KB Output is correct
9 Correct 37 ms 17956 KB Output is correct
10 Correct 29 ms 17892 KB Output is correct
11 Correct 50 ms 17936 KB Output is correct
12 Correct 25 ms 17856 KB Output is correct
13 Correct 41 ms 17996 KB Output is correct
14 Correct 53 ms 17996 KB Output is correct
15 Correct 14 ms 17612 KB Output is correct
16 Correct 18 ms 17664 KB Output is correct
17 Correct 16 ms 17784 KB Output is correct
18 Correct 13 ms 17612 KB Output is correct
19 Correct 21 ms 17992 KB Output is correct
20 Correct 15 ms 17612 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 577 ms 35220 KB Output is correct
2 Correct 187 ms 24584 KB Output is correct
3 Correct 1884 ms 53436 KB Output is correct
4 Correct 397 ms 28068 KB Output is correct
5 Execution timed out 3073 ms 52860 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17520 KB Output is correct
2 Correct 12 ms 17484 KB Output is correct
3 Correct 14 ms 17484 KB Output is correct
4 Correct 13 ms 17484 KB Output is correct
5 Correct 14 ms 17484 KB Output is correct
6 Correct 13 ms 17532 KB Output is correct
7 Correct 15 ms 17740 KB Output is correct
8 Correct 15 ms 17612 KB Output is correct
9 Correct 37 ms 17956 KB Output is correct
10 Correct 29 ms 17892 KB Output is correct
11 Correct 50 ms 17936 KB Output is correct
12 Correct 25 ms 17856 KB Output is correct
13 Correct 41 ms 17996 KB Output is correct
14 Correct 53 ms 17996 KB Output is correct
15 Correct 14 ms 17612 KB Output is correct
16 Correct 18 ms 17664 KB Output is correct
17 Correct 16 ms 17784 KB Output is correct
18 Correct 13 ms 17612 KB Output is correct
19 Correct 21 ms 17992 KB Output is correct
20 Correct 15 ms 17612 KB Output is correct
21 Correct 577 ms 35220 KB Output is correct
22 Correct 187 ms 24584 KB Output is correct
23 Correct 1884 ms 53436 KB Output is correct
24 Correct 397 ms 28068 KB Output is correct
25 Execution timed out 3073 ms 52860 KB Time limit exceeded
26 Halted 0 ms 0 KB -