oj.uz

답안 #406040

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
406040 2021-05-17T06:58:23 Z amunduzbaev 자매 도시 (APIO20_swap) C++14
13 / 100
 138 ms 14948 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;
		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]) 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(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});
			}
		} 
		
		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

# 결과 실행 시간 메모리 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 3 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 48 ms 8620 KB Output is correct
10 Correct 62 ms 9924 KB Output is correct
11 Correct 60 ms 9820 KB Output is correct
12 Correct 60 ms 10088 KB Output is correct
13 Correct 62 ms 10096 KB Output is correct
14 Correct 56 ms 8748 KB Output is correct
15 Correct 121 ms 11800 KB Output is correct
16 Correct 118 ms 11608 KB Output is correct
17 Correct 134 ms 11984 KB Output is correct
18 Correct 124 ms 11944 KB Output is correct
19 Correct 65 ms 7280 KB Output is correct
20 Correct 122 ms 12896 KB Output is correct
21 Correct 121 ms 12896 KB Output is correct
22 Correct 128 ms 13304 KB Output is correct
23 Correct 130 ms 13356 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 135 ms 14572 KB Output is correct
4 Correct 135 ms 14900 KB Output is correct
5 Correct 138 ms 14896 KB Output is correct
6 Correct 133 ms 14948 KB Output is correct
7 Correct 130 ms 14920 KB Output is correct
8 Correct 136 ms 14528 KB Output is correct
9 Correct 127 ms 14800 KB Output is correct
10 Correct 124 ms 14444 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 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 3 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 5 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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 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 3 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 48 ms 8620 KB Output is correct
11 Correct 62 ms 9924 KB Output is correct
12 Correct 60 ms 9820 KB Output is correct
13 Correct 60 ms 10088 KB Output is correct
14 Correct 62 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

# 결과 실행 시간 메모리 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 3 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 48 ms 8620 KB Output is correct
10 Correct 62 ms 9924 KB Output is correct
11 Correct 60 ms 9820 KB Output is correct
12 Correct 60 ms 10088 KB Output is correct
13 Correct 62 ms 10096 KB Output is correct
14 Correct 56 ms 8748 KB Output is correct
15 Correct 121 ms 11800 KB Output is correct
16 Correct 118 ms 11608 KB Output is correct
17 Correct 134 ms 11984 KB Output is correct
18 Correct 124 ms 11944 KB Output is correct
19 Correct 135 ms 14572 KB Output is correct
20 Correct 135 ms 14900 KB Output is correct
21 Correct 138 ms 14896 KB Output is correct
22 Correct 133 ms 14948 KB Output is correct
23 Correct 130 ms 14920 KB Output is correct
24 Correct 136 ms 14528 KB Output is correct
25 Correct 127 ms 14800 KB Output is correct
26 Correct 124 ms 14444 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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 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 3 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 48 ms 8620 KB Output is correct
11 Correct 62 ms 9924 KB Output is correct
12 Correct 60 ms 9820 KB Output is correct
13 Correct 60 ms 10088 KB Output is correct
14 Correct 62 ms 10096 KB Output is correct
15 Correct 56 ms 8748 KB Output is correct
16 Correct 121 ms 11800 KB Output is correct
17 Correct 118 ms 11608 KB Output is correct
18 Correct 134 ms 11984 KB Output is correct
19 Correct 124 ms 11944 KB Output is correct
20 Correct 135 ms 14572 KB Output is correct
21 Correct 135 ms 14900 KB Output is correct
22 Correct 138 ms 14896 KB Output is correct
23 Correct 133 ms 14948 KB Output is correct
24 Correct 130 ms 14920 KB Output is correct
25 Correct 136 ms 14528 KB Output is correct
26 Correct 127 ms 14800 KB Output is correct
27 Correct 124 ms 14444 KB Output is correct
28 Incorrect 3 ms 2636 KB Output isn't correct
29 Halted 0 ms 0 KB -