oj.uz

Submission #415577

# Submission time Handle Problem Language Result Execution time Memory
415577 2021-06-01T08:51:36 Z amoo_safar Robot (JOI21_ho_t4) C++17
0 / 100
 3000 ms 73496 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]] == 2) 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
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 36292 KB Output is correct
2 Correct 27 ms 36280 KB Output is correct
3 Correct 26 ms 36300 KB Output is correct
4 Correct 27 ms 36352 KB Output is correct
5 Correct 27 ms 36388 KB Output is correct
6 Correct 28 ms 36296 KB Output is correct
7 Correct 25 ms 36556 KB Output is correct
8 Correct 28 ms 36460 KB Output is correct
9 Correct 33 ms 36808 KB Output is correct
10 Correct 37 ms 36780 KB Output is correct
11 Correct 44 ms 36812 KB Output is correct
12 Correct 39 ms 36552 KB Output is correct
13 Correct 44 ms 36832 KB Output is correct
14 Correct 44 ms 36812 KB Output is correct
15 Correct 29 ms 36420 KB Output is correct
16 Incorrect 31 ms 36532 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 55916 KB Output is correct
2 Correct 238 ms 44484 KB Output is correct
3 Correct 1760 ms 73496 KB Output is correct
4 Correct 379 ms 48328 KB Output is correct
5 Execution timed out 3065 ms 72020 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 36292 KB Output is correct
2 Correct 27 ms 36280 KB Output is correct
3 Correct 26 ms 36300 KB Output is correct
4 Correct 27 ms 36352 KB Output is correct
5 Correct 27 ms 36388 KB Output is correct
6 Correct 28 ms 36296 KB Output is correct
7 Correct 25 ms 36556 KB Output is correct
8 Correct 28 ms 36460 KB Output is correct
9 Correct 33 ms 36808 KB Output is correct
10 Correct 37 ms 36780 KB Output is correct
11 Correct 44 ms 36812 KB Output is correct
12 Correct 39 ms 36552 KB Output is correct
13 Correct 44 ms 36832 KB Output is correct
14 Correct 44 ms 36812 KB Output is correct
15 Correct 29 ms 36420 KB Output is correct
16 Incorrect 31 ms 36532 KB Output isn't correct
17 Halted 0 ms 0 KB -