oj.uz

Submission #950132

# Submission time Handle Problem Language Result Execution time Memory
950132 2024-03-20T05:43:12 Z KiaRez Swapping Cities (APIO20_swap) C++17
6 / 100
 674 ms 134192 KB 
/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 3e5+23, lg = 19;
ll Mod = 1e9+7; //998244353;

inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

int n, m, h[N], ok[N], cnt, cnd[N], f[N], par[lg][N], mx[N];
int h2[N], p2[lg][N], mx2[lg][N], mx3[lg][N];
vector<pii> alle[N], adj[N], e;
vector<int> tree[N];

int getPar(int v) {return (f[v]==0 ? v : f[v]=getPar(f[v]));}

void merge(int v, int u, int w) {
	if(getPar(v) != getPar(u)) {
		adj[v].pb({u, w});
		adj[u].pb({v, w});
	}
	v=getPar(v), u=getPar(u);
	if(v == u) {
		ok[v] = 1, mx[cnd[v]] = min(mx[cnd[v]], w);
		return;
	}

	tree[cnt].pb(cnd[v]); tree[cnt].pb(cnd[u]);
	ok[v] |= ok[u];
	if(ok[v] == 1) mx[cnt] = w;
	cnd[v] = cnt;
	cnt++;
	f[u] = v;
}

void dfs_init(int v, int p=0) {
	h[v] = h[p] + 1, par[0][v] = (p==0 ? v : p);
	mx[v] = min(mx[v], mx[p]);
	for(int i=1; i<lg; i++) {
		par[i][v] = par[i-1][par[i-1][v]];
	}
	for(auto u : tree[v]) {
		//if(u == p) continue;
		dfs_init(u, v);
	}
}

int getF(int v, int dist) {
	for(int i=0; i<lg; i++) if((dist>>i)%2 == 1) {v = par[i][v];} return v;
}
int LCA(int v, int u) {
	if(h[v] > h[u]) swap(v, u);
	u = getF(u, h[u]-h[v]);
	if(v == u) return v;
	for(int i=lg-1; i>=0; i--) { if(par[i][v] != par[i][u]) v=par[i][v], u=par[i][u]; }
	return par[0][v];
}

int glob0, glob1;
int getF2(int v, int dist) {
	glob0 = 0, glob1 = 2e9;
	for(int i=0; i<lg; i++) if((dist>>i)%2 == 1) {
		glob0 = max(glob0, mx2[i][v]);
		glob1 = min(glob1, mx3[i][v]);
		v = p2[i][v];
	} return v;
}
int LCA2(int v, int u) {
	if(h2[v] > h2[u]) swap(v, u);
	u = getF2(u, h2[u]-h2[v]);
	if(v == u) return v;
	for(int i=lg-1; i>=0; i--) { if(p2[i][v] != p2[i][u]) v=p2[i][v], u=p2[i][u]; }
	return p2[0][v];
}

void dfs2(int v, int p=0) {
	h2[v] = h2[p] + 1, p2[0][v] = (p==0 ? v : p);
	//fuck(mx2[0][v]);
	if(p==0) mx2[0][v] = 2e9;
	for(int i=1; i<lg; i++) {
		p2[i][v] = p2[i-1][p2[i-1][v]];
		mx2[i][v] = max(mx2[i-1][v], mx2[i-1][p2[i-1][v]]);
		mx3[i][v] = min(mx3[i-1][v], mx3[i-1][p2[i-1][v]]);
	}
	for(auto u : adj[v]) {
		if(u.F == p) continue;
		mx2[0][u.F] = u.S;
		dfs2(u.F, v);
	}
}

void init(int _n, int _m, vector<int> V, vector<int> U, vector<int> W) {
	n=_n, m=_m, cnt=_n+1;
	for(int i=0; i<m; i++) {
		V[i]++, U[i]++;
		e.pb({W[i], i});
		alle[V[i]].pb({W[i], U[i]});
		alle[U[i]].pb({W[i], V[i]});
	}
	fill(mx, mx+N, (int)2e9);
	for(int i=0; i<N; i++) cnd[i] = i;
	for(int i=0; i<lg; i++) mx3[i][0] = mx2[i][0] = 2e9;
	for(int i=1; i<=n; i++) {
		sort(all(alle[i]));
		mx3[0][i] = 2e9;
		if(size(alle[i]) >= 3) mx3[0][i] = alle[i][2].F;
	}
	sort(all(e));
	for(auto it : e) {
		merge(V[it.S], U[it.S], it.F);
	}
	dfs2(1);
	dfs_init(cnd[getPar(1)]);
}

int getMinimumFuelCapacity(int v, int u) {
	v++, u++;
	int lca = LCA(v, u), lca2 = LCA2(v, u);
	if(m==n-1) return -1;
	int res0=0, res1=2e9;
	getF2(v, h2[v]-h2[lca2]); res0 = max(res0, glob0), res1 = min(res1, glob1);
	getF2(u, h2[u]-h2[lca2]); res0 = max(res0, glob0), res1 = min(res1, glob1);
	res1 = min(res1, mx3[0][lca2]);
	res0 = max(res0, res1);
	return min(mx[lca], res0);
}
/*
int main() {
	init(5, 6, {0, 0, 1, 1, 1, 2}, {1, 2, 2, 3, 4, 3}, {4, 4, 1, 2, 10, 3});
	cout<<getMinimumFuelCapacity(1, 2)<<endl;
	cout<<getMinimumFuelCapacity(2, 4)<<endl;
	cout<<getMinimumFuelCapacity(0, 1)<<endl;
	init(3, 2, {0, 0}, {1, 2}, {5, 5});
	cout<<getMinimumFuelCapacity(1, 2)<<endl;
	return 0;
}
*/

Compilation message

swap.cpp: In function 'int getF(int, int)':
swap.cpp:82:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   82 |  for(int i=0; i<lg; i++) if((dist>>i)%2 == 1) {v = par[i][v];} return v;
      |  ^~~
swap.cpp:82:64: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   82 |  for(int i=0; i<lg; i++) if((dist>>i)%2 == 1) {v = par[i][v];} return v;
      |                                                                ^~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 96976 KB Output is correct
2 Correct 14 ms 99040 KB Output is correct
3 Correct 14 ms 95212 KB Output is correct
4 Correct 14 ms 93020 KB Output is correct
5 Correct 14 ms 95392 KB Output is correct
6 Correct 14 ms 93276 KB Output is correct
7 Correct 14 ms 95384 KB Output is correct
8 Correct 14 ms 95448 KB Output is correct
9 Correct 178 ms 118984 KB Output is correct
10 Correct 226 ms 126408 KB Output is correct
11 Correct 210 ms 125204 KB Output is correct
12 Correct 224 ms 126660 KB Output is correct
13 Correct 208 ms 128196 KB Output is correct
14 Correct 227 ms 119720 KB Output is correct
15 Correct 535 ms 130280 KB Output is correct
16 Correct 581 ms 128536 KB Output is correct
17 Correct 496 ms 132356 KB Output is correct
18 Correct 615 ms 132360 KB Output is correct
19 Correct 129 ms 107200 KB Output is correct
20 Correct 604 ms 131824 KB Output is correct
21 Correct 631 ms 131348 KB Output is correct
22 Correct 630 ms 133880 KB Output is correct
23 Correct 674 ms 134192 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 96976 KB Output is correct
2 Correct 14 ms 99040 KB Output is correct
3 Incorrect 409 ms 131548 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 96976 KB Output is correct
2 Correct 14 ms 99040 KB Output is correct
3 Correct 14 ms 95212 KB Output is correct
4 Correct 14 ms 93020 KB Output is correct
5 Correct 14 ms 95392 KB Output is correct
6 Correct 14 ms 93276 KB Output is correct
7 Correct 14 ms 95384 KB Output is correct
8 Correct 14 ms 95448 KB Output is correct
9 Correct 14 ms 97116 KB Output is correct
10 Incorrect 16 ms 101672 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 97116 KB Output is correct
2 Correct 44 ms 96976 KB Output is correct
3 Correct 14 ms 99040 KB Output is correct
4 Correct 14 ms 95212 KB Output is correct
5 Correct 14 ms 93020 KB Output is correct
6 Correct 14 ms 95392 KB Output is correct
7 Correct 14 ms 93276 KB Output is correct
8 Correct 14 ms 95384 KB Output is correct
9 Correct 14 ms 95448 KB Output is correct
10 Correct 178 ms 118984 KB Output is correct
11 Correct 226 ms 126408 KB Output is correct
12 Correct 210 ms 125204 KB Output is correct
13 Correct 224 ms 126660 KB Output is correct
14 Correct 208 ms 128196 KB Output is correct
15 Incorrect 16 ms 101672 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 96976 KB Output is correct
2 Correct 14 ms 99040 KB Output is correct
3 Correct 14 ms 95212 KB Output is correct
4 Correct 14 ms 93020 KB Output is correct
5 Correct 14 ms 95392 KB Output is correct
6 Correct 14 ms 93276 KB Output is correct
7 Correct 14 ms 95384 KB Output is correct
8 Correct 14 ms 95448 KB Output is correct
9 Correct 178 ms 118984 KB Output is correct
10 Correct 226 ms 126408 KB Output is correct
11 Correct 210 ms 125204 KB Output is correct
12 Correct 224 ms 126660 KB Output is correct
13 Correct 208 ms 128196 KB Output is correct
14 Correct 227 ms 119720 KB Output is correct
15 Correct 535 ms 130280 KB Output is correct
16 Correct 581 ms 128536 KB Output is correct
17 Correct 496 ms 132356 KB Output is correct
18 Correct 615 ms 132360 KB Output is correct
19 Incorrect 409 ms 131548 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 97116 KB Output is correct
2 Correct 44 ms 96976 KB Output is correct
3 Correct 14 ms 99040 KB Output is correct
4 Correct 14 ms 95212 KB Output is correct
5 Correct 14 ms 93020 KB Output is correct
6 Correct 14 ms 95392 KB Output is correct
7 Correct 14 ms 93276 KB Output is correct
8 Correct 14 ms 95384 KB Output is correct
9 Correct 14 ms 95448 KB Output is correct
10 Correct 178 ms 118984 KB Output is correct
11 Correct 226 ms 126408 KB Output is correct
12 Correct 210 ms 125204 KB Output is correct
13 Correct 224 ms 126660 KB Output is correct
14 Correct 208 ms 128196 KB Output is correct
15 Correct 227 ms 119720 KB Output is correct
16 Correct 535 ms 130280 KB Output is correct
17 Correct 581 ms 128536 KB Output is correct
18 Correct 496 ms 132356 KB Output is correct
19 Correct 615 ms 132360 KB Output is correct
20 Incorrect 409 ms 131548 KB Output isn't correct
21 Halted 0 ms 0 KB -