oj.uz

Submission #949861

# Submission time Handle Problem Language Result Execution time Memory
949861 2024-03-19T19:08:59 Z KiaRez Swapping Cities (APIO20_swap) C++17
6 / 100
 231 ms 68384 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 = 5e5+23, lg = 20;
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];
vector<pii> 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) {
	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];
}

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});
	}
	fill(mx, mx+N, (int)2e9);
	for(int i=0; i<N; i++) cnd[i] = i;
	sort(all(e));
	for(auto it : e) {
		merge(V[it.S], U[it.S], it.F);
	}
	dfs_init(cnd[getPar(1)]);
}

int getMinimumFuelCapacity(int v, int u) {
	v++, u++;
	int lca = LCA(v, u);
	while(mx[lca]!=(int)2e9 && m==n-1) fuck("you");
	if(mx[lca] == 2e9) return -1;
	return mx[lca];
}
/*
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 18 ms 55900 KB Output is correct
2 Correct 10 ms 55900 KB Output is correct
3 Correct 8 ms 55900 KB Output is correct
4 Correct 9 ms 55932 KB Output is correct
5 Correct 9 ms 55900 KB Output is correct
6 Correct 11 ms 55900 KB Output is correct
7 Correct 9 ms 55992 KB Output is correct
8 Correct 10 ms 55900 KB Output is correct
9 Correct 76 ms 61896 KB Output is correct
10 Correct 95 ms 63180 KB Output is correct
11 Correct 95 ms 63216 KB Output is correct
12 Correct 105 ms 63660 KB Output is correct
13 Correct 85 ms 65148 KB Output is correct
14 Correct 86 ms 62032 KB Output is correct
15 Correct 195 ms 65104 KB Output is correct
16 Correct 188 ms 64892 KB Output is correct
17 Correct 199 ms 65324 KB Output is correct
18 Correct 215 ms 66808 KB Output is correct
19 Correct 71 ms 60452 KB Output is correct
20 Correct 187 ms 66324 KB Output is correct
21 Correct 192 ms 66184 KB Output is correct
22 Correct 213 ms 66604 KB Output is correct
23 Correct 231 ms 68384 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 55900 KB Output is correct
2 Correct 10 ms 55900 KB Output is correct
3 Incorrect 203 ms 67692 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 55900 KB Output is correct
2 Correct 10 ms 55900 KB Output is correct
3 Correct 8 ms 55900 KB Output is correct
4 Correct 9 ms 55932 KB Output is correct
5 Correct 9 ms 55900 KB Output is correct
6 Correct 11 ms 55900 KB Output is correct
7 Correct 9 ms 55992 KB Output is correct
8 Correct 10 ms 55900 KB Output is correct
9 Correct 8 ms 55896 KB Output is correct
10 Incorrect 9 ms 55900 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 55896 KB Output is correct
2 Correct 18 ms 55900 KB Output is correct
3 Correct 10 ms 55900 KB Output is correct
4 Correct 8 ms 55900 KB Output is correct
5 Correct 9 ms 55932 KB Output is correct
6 Correct 9 ms 55900 KB Output is correct
7 Correct 11 ms 55900 KB Output is correct
8 Correct 9 ms 55992 KB Output is correct
9 Correct 10 ms 55900 KB Output is correct
10 Correct 76 ms 61896 KB Output is correct
11 Correct 95 ms 63180 KB Output is correct
12 Correct 95 ms 63216 KB Output is correct
13 Correct 105 ms 63660 KB Output is correct
14 Correct 85 ms 65148 KB Output is correct
15 Incorrect 9 ms 55900 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 55900 KB Output is correct
2 Correct 10 ms 55900 KB Output is correct
3 Correct 8 ms 55900 KB Output is correct
4 Correct 9 ms 55932 KB Output is correct
5 Correct 9 ms 55900 KB Output is correct
6 Correct 11 ms 55900 KB Output is correct
7 Correct 9 ms 55992 KB Output is correct
8 Correct 10 ms 55900 KB Output is correct
9 Correct 76 ms 61896 KB Output is correct
10 Correct 95 ms 63180 KB Output is correct
11 Correct 95 ms 63216 KB Output is correct
12 Correct 105 ms 63660 KB Output is correct
13 Correct 85 ms 65148 KB Output is correct
14 Correct 86 ms 62032 KB Output is correct
15 Correct 195 ms 65104 KB Output is correct
16 Correct 188 ms 64892 KB Output is correct
17 Correct 199 ms 65324 KB Output is correct
18 Correct 215 ms 66808 KB Output is correct
19 Incorrect 203 ms 67692 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 55896 KB Output is correct
2 Correct 18 ms 55900 KB Output is correct
3 Correct 10 ms 55900 KB Output is correct
4 Correct 8 ms 55900 KB Output is correct
5 Correct 9 ms 55932 KB Output is correct
6 Correct 9 ms 55900 KB Output is correct
7 Correct 11 ms 55900 KB Output is correct
8 Correct 9 ms 55992 KB Output is correct
9 Correct 10 ms 55900 KB Output is correct
10 Correct 76 ms 61896 KB Output is correct
11 Correct 95 ms 63180 KB Output is correct
12 Correct 95 ms 63216 KB Output is correct
13 Correct 105 ms 63660 KB Output is correct
14 Correct 85 ms 65148 KB Output is correct
15 Correct 86 ms 62032 KB Output is correct
16 Correct 195 ms 65104 KB Output is correct
17 Correct 188 ms 64892 KB Output is correct
18 Correct 199 ms 65324 KB Output is correct
19 Correct 215 ms 66808 KB Output is correct
20 Incorrect 203 ms 67692 KB Output isn't correct
21 Halted 0 ms 0 KB -