oj.uz

Submission #950138

# Submission time Handle Problem Language Result Execution time Memory
950138 2024-03-20T05:51:50 Z KiaRez Swapping Cities (APIO20_swap) C++17
6 / 100
 820 ms 131060 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], deg[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});
	}
	deg[v]++, deg[u]++; int yey = 0;
	if(max(deg[v], deg[u]) >= 3) yey = 1;
	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];
	ok[v] |= yey;
	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;
	//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;
}
*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 101212 KB Output is correct
2 Correct 17 ms 101124 KB Output is correct
3 Correct 14 ms 101212 KB Output is correct
4 Correct 14 ms 101208 KB Output is correct
5 Correct 15 ms 101464 KB Output is correct
6 Correct 15 ms 101464 KB Output is correct
7 Correct 15 ms 103516 KB Output is correct
8 Correct 15 ms 101468 KB Output is correct
9 Correct 166 ms 122056 KB Output is correct
10 Correct 225 ms 127592 KB Output is correct
11 Correct 218 ms 126848 KB Output is correct
12 Correct 227 ms 128456 KB Output is correct
13 Correct 198 ms 129512 KB Output is correct
14 Correct 220 ms 121740 KB Output is correct
15 Correct 517 ms 130344 KB Output is correct
16 Correct 522 ms 127604 KB Output is correct
17 Correct 556 ms 131060 KB Output is correct
18 Correct 604 ms 130388 KB Output is correct
19 Correct 130 ms 109140 KB Output is correct
20 Correct 588 ms 130120 KB Output is correct
21 Correct 656 ms 128772 KB Output is correct
22 Correct 756 ms 118320 KB Output is correct
23 Correct 820 ms 122232 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 101212 KB Output is correct
2 Correct 17 ms 101124 KB Output is correct
3 Incorrect 404 ms 128156 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 101212 KB Output is correct
2 Correct 17 ms 101124 KB Output is correct
3 Correct 14 ms 101212 KB Output is correct
4 Correct 14 ms 101208 KB Output is correct
5 Correct 15 ms 101464 KB Output is correct
6 Correct 15 ms 101464 KB Output is correct
7 Correct 15 ms 103516 KB Output is correct
8 Correct 15 ms 101468 KB Output is correct
9 Correct 15 ms 113500 KB Output is correct
10 Incorrect 16 ms 111452 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 113500 KB Output is correct
2 Correct 29 ms 101212 KB Output is correct
3 Correct 17 ms 101124 KB Output is correct
4 Correct 14 ms 101212 KB Output is correct
5 Correct 14 ms 101208 KB Output is correct
6 Correct 15 ms 101464 KB Output is correct
7 Correct 15 ms 101464 KB Output is correct
8 Correct 15 ms 103516 KB Output is correct
9 Correct 15 ms 101468 KB Output is correct
10 Correct 166 ms 122056 KB Output is correct
11 Correct 225 ms 127592 KB Output is correct
12 Correct 218 ms 126848 KB Output is correct
13 Correct 227 ms 128456 KB Output is correct
14 Correct 198 ms 129512 KB Output is correct
15 Incorrect 16 ms 111452 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 101212 KB Output is correct
2 Correct 17 ms 101124 KB Output is correct
3 Correct 14 ms 101212 KB Output is correct
4 Correct 14 ms 101208 KB Output is correct
5 Correct 15 ms 101464 KB Output is correct
6 Correct 15 ms 101464 KB Output is correct
7 Correct 15 ms 103516 KB Output is correct
8 Correct 15 ms 101468 KB Output is correct
9 Correct 166 ms 122056 KB Output is correct
10 Correct 225 ms 127592 KB Output is correct
11 Correct 218 ms 126848 KB Output is correct
12 Correct 227 ms 128456 KB Output is correct
13 Correct 198 ms 129512 KB Output is correct
14 Correct 220 ms 121740 KB Output is correct
15 Correct 517 ms 130344 KB Output is correct
16 Correct 522 ms 127604 KB Output is correct
17 Correct 556 ms 131060 KB Output is correct
18 Correct 604 ms 130388 KB Output is correct
19 Incorrect 404 ms 128156 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 113500 KB Output is correct
2 Correct 29 ms 101212 KB Output is correct
3 Correct 17 ms 101124 KB Output is correct
4 Correct 14 ms 101212 KB Output is correct
5 Correct 14 ms 101208 KB Output is correct
6 Correct 15 ms 101464 KB Output is correct
7 Correct 15 ms 101464 KB Output is correct
8 Correct 15 ms 103516 KB Output is correct
9 Correct 15 ms 101468 KB Output is correct
10 Correct 166 ms 122056 KB Output is correct
11 Correct 225 ms 127592 KB Output is correct
12 Correct 218 ms 126848 KB Output is correct
13 Correct 227 ms 128456 KB Output is correct
14 Correct 198 ms 129512 KB Output is correct
15 Correct 220 ms 121740 KB Output is correct
16 Correct 517 ms 130344 KB Output is correct
17 Correct 522 ms 127604 KB Output is correct
18 Correct 556 ms 131060 KB Output is correct
19 Correct 604 ms 130388 KB Output is correct
20 Incorrect 404 ms 128156 KB Output isn't correct
21 Halted 0 ms 0 KB -