oj.uz

답안 #387874

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
387874 2021-04-09T10:39:43 Z AmShZ 자매 도시 (APIO20_swap) C++11
6 / 100
 931 ms 90876 KB 
// khodaya khodet komak kon
# include <bits/stdc++.h>
 
/*
// ordered_set 
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
# define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
*/
 
using namespace std;
 
typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <ll, ll>                                    pll;
typedef pair <pll,  ll>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
 
# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define InTheNameOfGod                                  ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
 
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
 
const int xn = 2e5 + 10;
const int xm = 10 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const int mod = 1e9 + 7;//998244353;
const int base = 257;

int dsu[xn], sz[xn], par[xm][xn];
int H[xn], mn[xn], a[xn], wp[xn];
pii mx[xm][xn];
bool inmst[xn];
set <pii> st[xn], ts[xn], S[xn];
vector <pip> E;
vector <pii> adj[xn], G[xn], vec;

int get_root(int v){
	if (v == dsu[v])
		return v;
	return dsu[v] = get_root(dsu[v]);
}
void preDFS(int v){
	for (int i = 1; i < xm; ++ i){
		par[i][v] = par[i - 1][par[i - 1][v]];
		mx[i][v].A = max(mx[i - 1][v].A, mx[i - 1][par[i - 1][v]].A);
		mx[i][v].B = min(mx[i - 1][v].B, mx[i - 1][par[i - 1][v]].B);
	}
	vec.clear();
	for (pii u : adj[v])
		if (u.A != par[0][v])
			vec.push_back({E[u.B].A, u.A}), S[v].insert({E[u.B].A, u.A});
	sort(all(vec));
	for (int i = 1; i < SZ(vec); ++ i)
		mx[0][vec[i].B].B = min(mn[v], vec[0].A);
	if (SZ(vec))
		mx[0][vec[0].B].B = mn[v];
	if (SZ(vec) > 1)
		mx[0][vec[0].B].B = min(mn[v], vec[1].A);
	for (pii u : adj[v]){
		if (u.A == par[0][v])
			continue;
		par[0][u.A] = v;
		mx[0][u.A].A = E[u.B].A;
		mx[0][u.A].B = mn[v];
		H[u.A] = H[v] + 1;
		wp[u.A] = E[u.B].A;
		preDFS(u.A);
	}
}
int LCA(int v, int u){
	if (H[v] > H[u])
		swap(v, u);
	for (int i = xm - 1; i >= 0; -- i)
		if ((1 << i) <= H[u] - H[v])
			u = par[i][u];
	if (v == u)
		return v;
	for (int i = xm - 1; i >= 0; -- i)
		if (par[i][v] != par[i][u])
			v = par[i][v], u = par[i][u];
	return par[0][v];
}
void merge(int v, int u){
	v = get_root(v);
	u = get_root(u);
	if (sz[v] < sz[u])
		swap(v, u);
	dsu[u] = v, sz[v] += sz[u];
	for (pii x : st[u])
		st[v].insert(x);
}
void DFS(int v){
	for (pii u : adj[v])
		if (u.A != par[0][v])
			DFS(u.A), merge(v, u.A);
	int rt = get_root(v);
	for (pii u : G[v]){
		int lca = LCA(v, u.A);
		st[rt].insert({E[u.B].A, u.B});
		ts[lca].insert({E[u.B].A, u.B});
	}
	for (pii x : ts[v])
		st[rt].erase(x);
	a[v] = inf;
	if (SZ(st[rt]))
		a[v] = st[rt].begin() -> A;
}
void init(int n, int m, vector <int> V, vector <int> U, vector <int> W){
	for (int i = 1; i <= n; ++ i)
		dsu[i] = i, sz[i] = 1;
	for (int i = 0; i < m; ++ i){
		int v = V[i] + 1, u = U[i] + 1, w = W[i];
		E.push_back({w, {v, u}});
	}
	sort(all(E));
	for (int i = 0; i < m; ++ i){
		pip e = E[i];
		int v = e.B.A, u = e.B.B, w = e.A;
		int pv = v, pu = u;
		v = get_root(v);
		u = get_root(u);
		if (v == u){
			G[pv].push_back({pu, i});
			G[pu].push_back({pv, i});
			continue;
		}
		if (sz[v] < sz[u])
			swap(v, u);
		inmst[i] = true;
		dsu[u] = v, sz[v] += sz[u];
		adj[pv].push_back({pu, i});
		adj[pu].push_back({pv, i});
	}
	for (int i = 1; i <= n; ++ i){
		dsu[i] = i, sz[i] = 1;
		mn[i] = inf;
		for (pii u : G[i])
			mn[i] = min(mn[i], E[u.B].A);
	}
	preDFS(1), DFS(1);
}
int getMinimumFuelCapacity(int v, int u){
	++ v, ++ u;
	int lca = LCA(v, u), res = inf, ans = 0;
	int pv = v, pu = u;
	if (H[v] > H[u])
		swap(v, u);
	for (int i = xm - 1; i >= 0; -- i){
		if (H[u] - H[v] < (1 << i))
			continue;
		ans = max(ans, mx[i][u].A);
		res = min(res, mx[i][u].B);
		u = par[i][u];
	}
	for (int i = xm - 1; i >= 0; -- i){
		if (par[i][v] == par[i][u])
			continue;
		ans = max(ans, mx[i][v].A);
		res = min(res, mx[i][v].B);
		ans = max(ans, mx[i][u].A);
		res = min(res, mx[i][u].B);
		v = par[i][v], u = par[i][u];
	}
	if (v != u){
		ans = max(ans, mx[0][v].A);
		ans = max(ans, mx[0][u].A);
		res = min(res, mn[lca]);
		for (pii x : S[lca]){
			if (x.B != v && x.B != u){
				res = min(res, x.A);
				break;
			}
		}
		if (lca - 1)
			res = min(res, wp[lca]);
	}
	v = pv, u = pu;
	res = min(res, min(a[v], a[u]));
	if (res == inf)
		return - 1;
	return max(ans, res);
}


/*
int n, m, q;
vector <int> V, U, W;

int main(){
	InTheNameOfGod;

	cin >> n >> m;
	for (int i = 0; i < m; ++ i){
		int v, u, w;
		cin >> v >> u >> w;
		V.push_back(v);
		U.push_back(u);
		W.push_back(w);
	}
	init(n, m, V, U, W);
	cin >> q;
	while (q --){
		int v, u;
		cin >> v >> u;
		cout << getMinimumFuelCapacity(v, u) << endl;
	}
		
	return 0;
}
5 6
0 1 4
0 2 4
1 4 10
1 3 2
1 2 1
2 3 3
3
1 2
2 4
0 1
*/

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:132:29: warning: unused variable 'w' [-Wunused-variable]
  132 |   int v = e.B.A, u = e.B.B, w = e.A;
      |                             ^

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 38096 KB Output is correct
2 Correct 22 ms 38048 KB Output is correct
3 Correct 22 ms 38124 KB Output is correct
4 Correct 26 ms 38360 KB Output is correct
5 Correct 26 ms 38584 KB Output is correct
6 Correct 22 ms 38468 KB Output is correct
7 Correct 23 ms 38560 KB Output is correct
8 Correct 23 ms 38656 KB Output is correct
9 Correct 254 ms 74204 KB Output is correct
10 Correct 332 ms 84552 KB Output is correct
11 Correct 332 ms 82828 KB Output is correct
12 Correct 363 ms 86024 KB Output is correct
13 Correct 305 ms 89204 KB Output is correct
14 Correct 303 ms 72964 KB Output is correct
15 Correct 888 ms 86116 KB Output is correct
16 Correct 868 ms 81980 KB Output is correct
17 Correct 812 ms 90876 KB Output is correct
18 Correct 804 ms 88396 KB Output is correct
19 Correct 181 ms 49668 KB Output is correct
20 Correct 887 ms 86128 KB Output is correct
21 Correct 788 ms 83116 KB Output is correct
22 Correct 931 ms 88168 KB Output is correct
23 Correct 847 ms 89156 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 38096 KB Output is correct
2 Correct 22 ms 38048 KB Output is correct
3 Incorrect 423 ms 77872 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 38096 KB Output is correct
2 Correct 22 ms 38048 KB Output is correct
3 Correct 22 ms 38124 KB Output is correct
4 Correct 26 ms 38360 KB Output is correct
5 Correct 26 ms 38584 KB Output is correct
6 Correct 22 ms 38468 KB Output is correct
7 Correct 23 ms 38560 KB Output is correct
8 Correct 23 ms 38656 KB Output is correct
9 Correct 22 ms 38156 KB Output is correct
10 Correct 25 ms 38548 KB Output is correct
11 Incorrect 24 ms 38604 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 38156 KB Output is correct
2 Correct 23 ms 38096 KB Output is correct
3 Correct 22 ms 38048 KB Output is correct
4 Correct 22 ms 38124 KB Output is correct
5 Correct 26 ms 38360 KB Output is correct
6 Correct 26 ms 38584 KB Output is correct
7 Correct 22 ms 38468 KB Output is correct
8 Correct 23 ms 38560 KB Output is correct
9 Correct 23 ms 38656 KB Output is correct
10 Correct 254 ms 74204 KB Output is correct
11 Correct 332 ms 84552 KB Output is correct
12 Correct 332 ms 82828 KB Output is correct
13 Correct 363 ms 86024 KB Output is correct
14 Correct 305 ms 89204 KB Output is correct
15 Correct 25 ms 38548 KB Output is correct
16 Incorrect 24 ms 38604 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 38096 KB Output is correct
2 Correct 22 ms 38048 KB Output is correct
3 Correct 22 ms 38124 KB Output is correct
4 Correct 26 ms 38360 KB Output is correct
5 Correct 26 ms 38584 KB Output is correct
6 Correct 22 ms 38468 KB Output is correct
7 Correct 23 ms 38560 KB Output is correct
8 Correct 23 ms 38656 KB Output is correct
9 Correct 254 ms 74204 KB Output is correct
10 Correct 332 ms 84552 KB Output is correct
11 Correct 332 ms 82828 KB Output is correct
12 Correct 363 ms 86024 KB Output is correct
13 Correct 305 ms 89204 KB Output is correct
14 Correct 303 ms 72964 KB Output is correct
15 Correct 888 ms 86116 KB Output is correct
16 Correct 868 ms 81980 KB Output is correct
17 Correct 812 ms 90876 KB Output is correct
18 Correct 804 ms 88396 KB Output is correct
19 Incorrect 423 ms 77872 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 38156 KB Output is correct
2 Correct 23 ms 38096 KB Output is correct
3 Correct 22 ms 38048 KB Output is correct
4 Correct 22 ms 38124 KB Output is correct
5 Correct 26 ms 38360 KB Output is correct
6 Correct 26 ms 38584 KB Output is correct
7 Correct 22 ms 38468 KB Output is correct
8 Correct 23 ms 38560 KB Output is correct
9 Correct 23 ms 38656 KB Output is correct
10 Correct 254 ms 74204 KB Output is correct
11 Correct 332 ms 84552 KB Output is correct
12 Correct 332 ms 82828 KB Output is correct
13 Correct 363 ms 86024 KB Output is correct
14 Correct 305 ms 89204 KB Output is correct
15 Correct 303 ms 72964 KB Output is correct
16 Correct 888 ms 86116 KB Output is correct
17 Correct 868 ms 81980 KB Output is correct
18 Correct 812 ms 90876 KB Output is correct
19 Correct 804 ms 88396 KB Output is correct
20 Incorrect 423 ms 77872 KB Output isn't correct
21 Halted 0 ms 0 KB -