oj.uz

Submission #406044

# Submission time Handle Problem Language Result Execution time Memory
406044 2021-05-17T07:02:52 Z amunduzbaev Swapping Cities (APIO20_swap) C++14
13 / 100
 187 ms 14964 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;
	if(n <= 1000){
		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;
		vector<int> bads;
		while(~tt){
			bads.pb(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]) 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);
				}
			}
		}
		
		//for(int i=0;i<sz(bads)-1;i++){
			//int a = bads[i], b = bads[i+1];
			//qq.push({0, x});
			//for(int i=0;i<n;i++) mn[i] = mod;
			//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(x.ff == a && u.ss == b) continue;
					//if(x.ff == b && u.ss == a) continue;
					//if(umin(mn[x.ff], max(mn[u.ss], x.ss))) qq.push({-mn[x.ff], x.ff});
				//}
			//} 
		//}
		
		for(auto xx : edges[x]) if(bad[xx.ff]) nall.pb({xx.ff, x});
		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]);
		
		nall.clear();
		for(auto xx : edges[y]) if(bad[xx.ff]) nall.pb({xx.ff, y});
		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]);
		
		if(rr == mod) return -1;
		return max(rr, trr);
	}
	
	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 2636 KB Output is correct
2 Correct 4 ms 4952 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 3 ms 2636 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 3 ms 2636 KB Output is correct
9 Correct 47 ms 8544 KB Output is correct
10 Correct 71 ms 9932 KB Output is correct
11 Correct 60 ms 9772 KB Output is correct
12 Correct 64 ms 10100 KB Output is correct
13 Correct 65 ms 10096 KB Output is correct
14 Correct 55 ms 8644 KB Output is correct
15 Correct 125 ms 11712 KB Output is correct
16 Correct 119 ms 11636 KB Output is correct
17 Correct 153 ms 11888 KB Output is correct
18 Correct 128 ms 11948 KB Output is correct
19 Correct 71 ms 7284 KB Output is correct
20 Correct 129 ms 12932 KB Output is correct
21 Correct 133 ms 12888 KB Output is correct
22 Correct 134 ms 13308 KB Output is correct
23 Correct 166 ms 13392 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 4 ms 4952 KB Output is correct
3 Correct 126 ms 14632 KB Output is correct
4 Correct 138 ms 14964 KB Output is correct
5 Correct 144 ms 14828 KB Output is correct
6 Correct 136 ms 14936 KB Output is correct
7 Correct 141 ms 14916 KB Output is correct
8 Correct 130 ms 14556 KB Output is correct
9 Correct 187 ms 14796 KB Output is correct
10 Correct 137 ms 14440 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 4 ms 4952 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 3 ms 2636 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 3 ms 2636 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Incorrect 3 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 4 ms 4940 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 4 ms 4952 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 3 ms 2636 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 3 ms 2636 KB Output is correct
9 Correct 3 ms 2636 KB Output is correct
10 Correct 47 ms 8544 KB Output is correct
11 Correct 71 ms 9932 KB Output is correct
12 Correct 60 ms 9772 KB Output is correct
13 Correct 64 ms 10100 KB Output is correct
14 Correct 65 ms 10096 KB Output is correct
15 Incorrect 3 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 2636 KB Output is correct
2 Correct 4 ms 4952 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 3 ms 2636 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 3 ms 2636 KB Output is correct
9 Correct 47 ms 8544 KB Output is correct
10 Correct 71 ms 9932 KB Output is correct
11 Correct 60 ms 9772 KB Output is correct
12 Correct 64 ms 10100 KB Output is correct
13 Correct 65 ms 10096 KB Output is correct
14 Correct 55 ms 8644 KB Output is correct
15 Correct 125 ms 11712 KB Output is correct
16 Correct 119 ms 11636 KB Output is correct
17 Correct 153 ms 11888 KB Output is correct
18 Correct 128 ms 11948 KB Output is correct
19 Correct 126 ms 14632 KB Output is correct
20 Correct 138 ms 14964 KB Output is correct
21 Correct 144 ms 14828 KB Output is correct
22 Correct 136 ms 14936 KB Output is correct
23 Correct 141 ms 14916 KB Output is correct
24 Correct 130 ms 14556 KB Output is correct
25 Correct 187 ms 14796 KB Output is correct
26 Correct 137 ms 14440 KB Output is correct
27 Incorrect 3 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 4 ms 4940 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 4 ms 4952 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 3 ms 2636 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 3 ms 2636 KB Output is correct
9 Correct 3 ms 2636 KB Output is correct
10 Correct 47 ms 8544 KB Output is correct
11 Correct 71 ms 9932 KB Output is correct
12 Correct 60 ms 9772 KB Output is correct
13 Correct 64 ms 10100 KB Output is correct
14 Correct 65 ms 10096 KB Output is correct
15 Correct 55 ms 8644 KB Output is correct
16 Correct 125 ms 11712 KB Output is correct
17 Correct 119 ms 11636 KB Output is correct
18 Correct 153 ms 11888 KB Output is correct
19 Correct 128 ms 11948 KB Output is correct
20 Correct 126 ms 14632 KB Output is correct
21 Correct 138 ms 14964 KB Output is correct
22 Correct 144 ms 14828 KB Output is correct
23 Correct 136 ms 14936 KB Output is correct
24 Correct 141 ms 14916 KB Output is correct
25 Correct 130 ms 14556 KB Output is correct
26 Correct 187 ms 14796 KB Output is correct
27 Correct 137 ms 14440 KB Output is correct
28 Incorrect 3 ms 2636 KB Output isn't correct
29 Halted 0 ms 0 KB -