oj.uz

Submission #405979

# Submission time Handle Problem Language Result Execution time Memory
405979 2021-05-17T06:03:27 Z amunduzbaev Swapping Cities (APIO20_swap) C++14
13 / 100
 149 ms 15284 KB 
#include "swap.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define int long long
template<class T> bool umin(T& a, const T b) { if(a > b) { a = b; return 1; } return 0; }
template<class T> bool umax(T& a, const T b) { if(a < b) { a = b; return 1; } return 0; }

const int NN = 1e5+5;
int mx = 0, ok, res, d[NN], n, m;
vector<pair<int, int>> edges[NN];
vector<pair<int, int>> mm;

void init(int32_t N, int32_t M,
	vector<int32_t> a, vector<int32_t> b, vector<int32_t> c) {
	n = N, m = M;
	for(int i=0;i<m;i++){
		edges[a[i]].pb({b[i], c[i]});
		edges[b[i]].pb({a[i], c[i]});
		mx = max(mx, (int)c[i]);
	}
	
	if(n == m) { ok = -1, res = mx; }
	else if(n == m+1){
		res = -1;
		ok = 1;
		for(int i=0;i<m;i++) ok &= (min(a[i], b[i]) == 0);
		if(ok){
			for(int i=0;i<m;i++) d[max(a[i], b[i])] = c[i];
			for(int i=1;i<n;i++) mm.pb({d[i], i});
			sort(mm.begin(), mm.end());
			mm.resize(3);
		} else ok = -1;
	} 
}

/*

5 6
0 1 4
0 2 4
1 2 1
1 3 2
2 3 3
1 4 10
3
1 2
2 4
0 1

*/

const int mod = 1e9+7;
int mn[NN], par[NN], bad[NN];

int32_t getMinimumFuelCapacity(int32_t x, int32_t y) {
	if(ok == -1) return res;
	if(x > y) swap(x, y);
	if(n == 2) return -1;
	cout<<"\n";
	if(n <= 1000 && !ok){
		priority_queue<pair<int, int>> qq;
		qq.push({0, x});
		memset(mn, 127, sizeof mn);
		memset(bad, 0, sizeof bad);
		memset(par, 0, sizeof par);
		par[x] = -1;
		mn[x] = 0;
		while(!qq.empty()){
			auto u = qq.top(); qq.pop();
			if(mn[u.ss] < -u.ff) continue;
			for(auto x : edges[u.ss]) if(umin(mn[x.ff], max(mn[u.ss], x.ss))) par[x.ff] = u.ss, qq.push({-mn[x.ff], x.ff});
		}
		int trr = mn[y];
		int tt = y;
		while(~tt){
			bad[tt] = 1;
			tt = par[tt];
		}
		
		int rr = mod;
		vector<pair<int, int>> nall;
		for(int i=0;i<n;i++){
			if(bad[i]){
				if(i == y || i == x){
					int mn = mod, in = -1, mn2 = mod;
					for(auto x : edges[i]){
						if(bad[x.ff]) { nall.pb({i, x.ff}); continue; }
						if(umin(mn, x.ss)) in = x.ff;
					} for(auto x : edges[i]){
						if(bad[x.ff] || in == x.ff) continue;
						umin(mn2, x.ss);
					} umin(rr, mn2);
					//cout<<mn<<" "<<mn2<<"\n";
				} else {
					int mn = mod;
					for(auto x : edges[i]){
						if(bad[x.ff]) continue;
						umin(mn, x.ss);
					} umin(rr, mn);
				}
			}
		}
		qq.push({0, x});
		memset(mn, 127, sizeof mn);
		mn[x] = 0;
		while(!qq.empty()){
			auto u = qq.top(); qq.pop();
			if(mn[u.ss] < -u.ff) continue;
			for(auto x : edges[u.ss]){
				int ok = 1;
				for(auto xx : nall) if(xx == make_pair(u.ss, x.ff) || xx == make_pair(x.ff, u.ss)) ok = 0;
				if(ok && umin(mn[x.ff], max(mn[u.ss], x.ss))) qq.push({-mn[x.ff], x.ff});
			}
		} umin(rr, mn[y]);
		//for(int i=0;i<n;i++) cout<<mn[i]<<" ";
		//cout<<"\n";
		umax(rr, trr);
		if(rr == mod) return -1;
		return rr;
	}
	
	if(x == 0){
		if(y == mm[0].ss || y == mm[1].ss || y == mm[2].ss) return max({mm[0].ff, mm[1].ff, mm[2].ff});
		else return max({d[y], mm[0].ff, mm[1].ff});
	} else {
		if(n == 3) return -1;
		if((mm[0].ss == y || mm[1].ss == y) && (mm[0].ss == x || mm[1].ss == x)) return max({d[x], d[y], mm[2].ff});
		else if(x == mm[0].ss || y == mm[0].ss) return max({d[x], d[y], mm[1].ff});
		else return max({d[x], d[y], mm[0].ff});
	} 
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 52 ms 8564 KB Output is correct
10 Correct 67 ms 9920 KB Output is correct
11 Correct 66 ms 9788 KB Output is correct
12 Correct 76 ms 10100 KB Output is correct
13 Correct 63 ms 10100 KB Output is correct
14 Correct 55 ms 8692 KB Output is correct
15 Correct 135 ms 11876 KB Output is correct
16 Correct 140 ms 11548 KB Output is correct
17 Correct 129 ms 11936 KB Output is correct
18 Correct 125 ms 11896 KB Output is correct
19 Correct 63 ms 7236 KB Output is correct
20 Correct 126 ms 12808 KB Output is correct
21 Correct 128 ms 12884 KB Output is correct
22 Correct 149 ms 13392 KB Output is correct
23 Correct 130 ms 13304 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 132 ms 14668 KB Output is correct
4 Correct 133 ms 15252 KB Output is correct
5 Correct 142 ms 15284 KB Output is correct
6 Correct 131 ms 15264 KB Output is correct
7 Correct 133 ms 15280 KB Output is correct
8 Correct 137 ms 15104 KB Output is correct
9 Correct 132 ms 15160 KB Output is correct
10 Correct 133 ms 14856 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Incorrect 2 ms 2636 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 3 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 52 ms 8564 KB Output is correct
11 Correct 67 ms 9920 KB Output is correct
12 Correct 66 ms 9788 KB Output is correct
13 Correct 76 ms 10100 KB Output is correct
14 Correct 63 ms 10100 KB Output is correct
15 Incorrect 2 ms 2636 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 52 ms 8564 KB Output is correct
10 Correct 67 ms 9920 KB Output is correct
11 Correct 66 ms 9788 KB Output is correct
12 Correct 76 ms 10100 KB Output is correct
13 Correct 63 ms 10100 KB Output is correct
14 Correct 55 ms 8692 KB Output is correct
15 Correct 135 ms 11876 KB Output is correct
16 Correct 140 ms 11548 KB Output is correct
17 Correct 129 ms 11936 KB Output is correct
18 Correct 125 ms 11896 KB Output is correct
19 Correct 132 ms 14668 KB Output is correct
20 Correct 133 ms 15252 KB Output is correct
21 Correct 142 ms 15284 KB Output is correct
22 Correct 131 ms 15264 KB Output is correct
23 Correct 133 ms 15280 KB Output is correct
24 Correct 137 ms 15104 KB Output is correct
25 Correct 132 ms 15160 KB Output is correct
26 Correct 133 ms 14856 KB Output is correct
27 Incorrect 2 ms 2636 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 3 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 52 ms 8564 KB Output is correct
11 Correct 67 ms 9920 KB Output is correct
12 Correct 66 ms 9788 KB Output is correct
13 Correct 76 ms 10100 KB Output is correct
14 Correct 63 ms 10100 KB Output is correct
15 Correct 55 ms 8692 KB Output is correct
16 Correct 135 ms 11876 KB Output is correct
17 Correct 140 ms 11548 KB Output is correct
18 Correct 129 ms 11936 KB Output is correct
19 Correct 125 ms 11896 KB Output is correct
20 Correct 132 ms 14668 KB Output is correct
21 Correct 133 ms 15252 KB Output is correct
22 Correct 142 ms 15284 KB Output is correct
23 Correct 131 ms 15264 KB Output is correct
24 Correct 133 ms 15280 KB Output is correct
25 Correct 137 ms 15104 KB Output is correct
26 Correct 132 ms 15160 KB Output is correct
27 Correct 133 ms 14856 KB Output is correct
28 Incorrect 2 ms 2636 KB Output isn't correct
29 Halted 0 ms 0 KB -