oj.uz

Submission #415584

# Submission time Handle Problem Language Result Execution time Memory
415584 2021-06-01T08:55:34 Z amoo_safar Robot (JOI21_ho_t4) C++17
34 / 100
 3000 ms 73844 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> 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 {

			// }
		} 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 28 ms 36300 KB Output is correct
2 Correct 19 ms 36300 KB Output is correct
3 Correct 20 ms 36356 KB Output is correct
4 Correct 24 ms 36288 KB Output is correct
5 Correct 25 ms 36300 KB Output is correct
6 Correct 20 ms 36376 KB Output is correct
7 Correct 24 ms 36608 KB Output is correct
8 Correct 24 ms 36484 KB Output is correct
9 Correct 38 ms 36756 KB Output is correct
10 Correct 44 ms 36752 KB Output is correct
11 Correct 39 ms 36840 KB Output is correct
12 Correct 40 ms 36652 KB Output is correct
13 Correct 46 ms 36808 KB Output is correct
14 Correct 45 ms 36708 KB Output is correct
15 Correct 23 ms 36500 KB Output is correct
16 Correct 30 ms 36556 KB Output is correct
17 Correct 27 ms 36608 KB Output is correct
18 Correct 23 ms 36428 KB Output is correct
19 Correct 31 ms 36784 KB Output is correct
20 Correct 27 ms 36516 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 697 ms 56044 KB Output is correct
2 Correct 220 ms 44704 KB Output is correct
3 Correct 1685 ms 73844 KB Output is correct
4 Correct 342 ms 48392 KB Output is correct
5 Execution timed out 3061 ms 71984 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 36300 KB Output is correct
2 Correct 19 ms 36300 KB Output is correct
3 Correct 20 ms 36356 KB Output is correct
4 Correct 24 ms 36288 KB Output is correct
5 Correct 25 ms 36300 KB Output is correct
6 Correct 20 ms 36376 KB Output is correct
7 Correct 24 ms 36608 KB Output is correct
8 Correct 24 ms 36484 KB Output is correct
9 Correct 38 ms 36756 KB Output is correct
10 Correct 44 ms 36752 KB Output is correct
11 Correct 39 ms 36840 KB Output is correct
12 Correct 40 ms 36652 KB Output is correct
13 Correct 46 ms 36808 KB Output is correct
14 Correct 45 ms 36708 KB Output is correct
15 Correct 23 ms 36500 KB Output is correct
16 Correct 30 ms 36556 KB Output is correct
17 Correct 27 ms 36608 KB Output is correct
18 Correct 23 ms 36428 KB Output is correct
19 Correct 31 ms 36784 KB Output is correct
20 Correct 27 ms 36516 KB Output is correct
21 Correct 697 ms 56044 KB Output is correct
22 Correct 220 ms 44704 KB Output is correct
23 Correct 1685 ms 73844 KB Output is correct
24 Correct 342 ms 48392 KB Output is correct
25 Execution timed out 3061 ms 71984 KB Time limit exceeded
26 Halted 0 ms 0 KB -