oj.uz

Submission #406047

# Submission time Handle Problem Language Result Execution time Memory
406047 2021-05-17T07:05:51 Z amunduzbaev Swapping Cities (APIO20_swap) C++14
13 / 100
 131 ms 15080 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) || (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});
				}
			} umin(rr, mn[y]);
		}
		
		//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 3 ms 4940 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 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 3 ms 2636 KB Output is correct
9 Correct 48 ms 8644 KB Output is correct
10 Correct 59 ms 9920 KB Output is correct
11 Correct 58 ms 9784 KB Output is correct
12 Correct 63 ms 10104 KB Output is correct
13 Correct 63 ms 10084 KB Output is correct
14 Correct 52 ms 8696 KB Output is correct
15 Correct 128 ms 11752 KB Output is correct
16 Correct 125 ms 11616 KB Output is correct
17 Correct 123 ms 11984 KB Output is correct
18 Correct 122 ms 11996 KB Output is correct
19 Correct 62 ms 7236 KB Output is correct
20 Correct 127 ms 12868 KB Output is correct
21 Correct 124 ms 12928 KB Output is correct
22 Correct 128 ms 13408 KB Output is correct
23 Correct 129 ms 13356 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 3 ms 4940 KB Output is correct
3 Correct 124 ms 14628 KB Output is correct
4 Correct 124 ms 15028 KB Output is correct
5 Correct 129 ms 14824 KB Output is correct
6 Correct 124 ms 15080 KB Output is correct
7 Correct 130 ms 14916 KB Output is correct
8 Correct 124 ms 14584 KB Output is correct
9 Correct 131 ms 14728 KB Output is correct
10 Correct 127 ms 14516 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 3 ms 4940 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 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 3 ms 2636 KB Output is correct
9 Correct 3 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 3 ms 4940 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 3 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 3 ms 2636 KB Output is correct
10 Correct 48 ms 8644 KB Output is correct
11 Correct 59 ms 9920 KB Output is correct
12 Correct 58 ms 9784 KB Output is correct
13 Correct 63 ms 10104 KB Output is correct
14 Correct 63 ms 10084 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 3 ms 4940 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 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 3 ms 2636 KB Output is correct
9 Correct 48 ms 8644 KB Output is correct
10 Correct 59 ms 9920 KB Output is correct
11 Correct 58 ms 9784 KB Output is correct
12 Correct 63 ms 10104 KB Output is correct
13 Correct 63 ms 10084 KB Output is correct
14 Correct 52 ms 8696 KB Output is correct
15 Correct 128 ms 11752 KB Output is correct
16 Correct 125 ms 11616 KB Output is correct
17 Correct 123 ms 11984 KB Output is correct
18 Correct 122 ms 11996 KB Output is correct
19 Correct 124 ms 14628 KB Output is correct
20 Correct 124 ms 15028 KB Output is correct
21 Correct 129 ms 14824 KB Output is correct
22 Correct 124 ms 15080 KB Output is correct
23 Correct 130 ms 14916 KB Output is correct
24 Correct 124 ms 14584 KB Output is correct
25 Correct 131 ms 14728 KB Output is correct
26 Correct 127 ms 14516 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 3 ms 4940 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 3 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 3 ms 2636 KB Output is correct
10 Correct 48 ms 8644 KB Output is correct
11 Correct 59 ms 9920 KB Output is correct
12 Correct 58 ms 9784 KB Output is correct
13 Correct 63 ms 10104 KB Output is correct
14 Correct 63 ms 10084 KB Output is correct
15 Correct 52 ms 8696 KB Output is correct
16 Correct 128 ms 11752 KB Output is correct
17 Correct 125 ms 11616 KB Output is correct
18 Correct 123 ms 11984 KB Output is correct
19 Correct 122 ms 11996 KB Output is correct
20 Correct 124 ms 14628 KB Output is correct
21 Correct 124 ms 15028 KB Output is correct
22 Correct 129 ms 14824 KB Output is correct
23 Correct 124 ms 15080 KB Output is correct
24 Correct 130 ms 14916 KB Output is correct
25 Correct 124 ms 14584 KB Output is correct
26 Correct 131 ms 14728 KB Output is correct
27 Correct 127 ms 14516 KB Output is correct
28 Incorrect 3 ms 2636 KB Output isn't correct
29 Halted 0 ms 0 KB -