oj.uz

Submission #406298

# Submission time Handle Problem Language Result Execution time Memory
406298 2021-05-17T10:39:07 Z amunduzbaev Swapping Cities (APIO20_swap) C++14
0 / 100
 41 ms 77748 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 N = 3e5+5;
const int mod = 1e9+7;

int n, m, par[N], d[N], f[N], w[N];
vector<int> edges[N];
int lca[N][30], tin[N], tout[N], t;

int fx(int x) { return (x == par[x] ? x : par[x] = fx(par[x])); }
void merge(int a, int b, int c){
	d[a]++, d[b]++;
	int cnd = (max(d[a], d[b]) >= 3);
	a = fx(a), b = fx(b);
	edges[n].pb(a);
	if(b != a) edges[n].pb(b);
	if(a == b){
		par[a] = par[b] = n;
		par[n] = n, f[n] = 1, w[n] = c;
	} else {
		par[a] = par[b] = n, w[n] = c;
		par[n] = n, f[n] = f[a] | f[b] | cnd;
	} n++;
}

void dfs(int u, int p){
	tin[u] = t++;
	lca[u][0] = p;
	for(int j=1;j<30;j++) lca[u][j] = lca[lca[u][j-1]][j-1];
	for(auto x : edges[u]) dfs(x, u);
	tout[u] = t - 1;
}

void init(int32_t N, int32_t M,
	vector<int32_t> a, vector<int32_t> b, vector<int32_t> c) {
	n = N, m = M;
	vector<array<int, 3>> tt;
	for(int i=0;i<m;i++) tt.pb({c[i], a[i], b[i]});
	sort(tt.begin(), tt.end());
	for(int i=0;i<n;i++) par[i] = i;
	for(auto x : tt) merge(x[1], x[2], x[0]);
	//for(int i=n-1;i>=0;i--){
		//for(auto x : edges[i]) cout<<x<<" "<<i<<"\n";
	//}
	memset(lca, -1, sizeof lca);
	dfs(n-1, n-1);
}

bool up(int a, int b) { return (tin[a] <= tin[b] && tout[b] <= tout[a]); }

int f_lca(int a, int b){
	if(up(b, a)) return b;
	if(up(a, b)) return a;
	for(int i=29;i>=0;i--){
		if(up(lca[a][i], b)) continue;
		a = lca[a][i];
	} return lca[a][0];
}

/*

5 5
0 1 0
1 2 1
2 3 2
3 4 3
0 4 4
5
0 1
1 2
2 3
3 4
0 4

*/

int32_t getMinimumFuelCapacity(int32_t x, int32_t y) {
	int lc = f_lca(x, y);
	if(f[lc]) return w[lc];
	for(int i=29;i>=0;i--){
		if(f[lca[lc][i]]) continue;
		lc = lca[lc][i];
	} return w[lca[lc][0]];
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 77748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 77748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 77748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 77748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 77748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 77748 KB Output isn't correct
2 Halted 0 ms 0 KB -