oj.uz

Submission #415542

# Submission time Handle Problem Language Result Execution time Memory
415542 2021-06-01T08:28:09 Z amoo_safar Robot (JOI21_ho_t4) C++17
0 / 100
 3000 ms 51932 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];

int dis[2][N]; // 0 -> Null, 1 -> fixed

ll sm[N], cost[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;
	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];
		// 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[ch] && 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 11 ms 12860 KB Output is correct
2 Correct 10 ms 12876 KB Output is correct
3 Correct 10 ms 12876 KB Output is correct
4 Correct 9 ms 12796 KB Output is correct
5 Correct 11 ms 12876 KB Output is correct
6 Correct 10 ms 12876 KB Output is correct
7 Correct 14 ms 12936 KB Output is correct
8 Correct 9 ms 12876 KB Output is correct
9 Incorrect 32 ms 13264 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 32352 KB Output is correct
2 Correct 133 ms 20544 KB Output is correct
3 Correct 1189 ms 51328 KB Output is correct
4 Correct 306 ms 24368 KB Output is correct
5 Execution timed out 3069 ms 51932 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12860 KB Output is correct
2 Correct 10 ms 12876 KB Output is correct
3 Correct 10 ms 12876 KB Output is correct
4 Correct 9 ms 12796 KB Output is correct
5 Correct 11 ms 12876 KB Output is correct
6 Correct 10 ms 12876 KB Output is correct
7 Correct 14 ms 12936 KB Output is correct
8 Correct 9 ms 12876 KB Output is correct
9 Incorrect 32 ms 13264 KB Output isn't correct
10 Halted 0 ms 0 KB -