oj.uz

Submission #949857

# Submission time Handle Problem Language Result Execution time Memory
949857 2024-03-19T19:05:45 Z KiaRez Swapping Cities (APIO20_swap) C++17
6 / 100
 246 ms 69108 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);
	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 20 ms 55900 KB Output is correct
2 Correct 10 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 55900 KB Output is correct
6 Correct 9 ms 56112 KB Output is correct
7 Correct 11 ms 55900 KB Output is correct
8 Correct 10 ms 55900 KB Output is correct
9 Correct 84 ms 61828 KB Output is correct
10 Correct 98 ms 63136 KB Output is correct
11 Correct 108 ms 63216 KB Output is correct
12 Correct 105 ms 63632 KB Output is correct
13 Correct 89 ms 65932 KB Output is correct
14 Correct 83 ms 61892 KB Output is correct
15 Correct 204 ms 65108 KB Output is correct
16 Correct 186 ms 64884 KB Output is correct
17 Correct 204 ms 65340 KB Output is correct
18 Correct 234 ms 67696 KB Output is correct
19 Correct 74 ms 60748 KB Output is correct
20 Correct 187 ms 66116 KB Output is correct
21 Correct 204 ms 66316 KB Output is correct
22 Correct 196 ms 66608 KB Output is correct
23 Correct 219 ms 68996 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 55900 KB Output is correct
2 Correct 10 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 55900 KB Output is correct
6 Correct 9 ms 56112 KB Output is correct
7 Correct 11 ms 55900 KB Output is correct
8 Correct 10 ms 55900 KB Output is correct
9 Correct 8 ms 55900 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 55900 KB Output is correct
2 Correct 20 ms 55900 KB Output is correct
3 Correct 10 ms 55900 KB Output is correct
4 Correct 10 ms 55900 KB Output is correct
5 Correct 8 ms 55900 KB Output is correct
6 Correct 9 ms 55900 KB Output is correct
7 Correct 9 ms 56112 KB Output is correct
8 Correct 11 ms 55900 KB Output is correct
9 Correct 10 ms 55900 KB Output is correct
10 Correct 84 ms 61828 KB Output is correct
11 Correct 98 ms 63136 KB Output is correct
12 Correct 108 ms 63216 KB Output is correct
13 Correct 105 ms 63632 KB Output is correct
14 Correct 89 ms 65932 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 20 ms 55900 KB Output is correct
2 Correct 10 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 55900 KB Output is correct
6 Correct 9 ms 56112 KB Output is correct
7 Correct 11 ms 55900 KB Output is correct
8 Correct 10 ms 55900 KB Output is correct
9 Correct 84 ms 61828 KB Output is correct
10 Correct 98 ms 63136 KB Output is correct
11 Correct 108 ms 63216 KB Output is correct
12 Correct 105 ms 63632 KB Output is correct
13 Correct 89 ms 65932 KB Output is correct
14 Correct 83 ms 61892 KB Output is correct
15 Correct 204 ms 65108 KB Output is correct
16 Correct 186 ms 64884 KB Output is correct
17 Correct 204 ms 65340 KB Output is correct
18 Correct 234 ms 67696 KB Output is correct
19 Incorrect 246 ms 69108 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 55900 KB Output is correct
2 Correct 20 ms 55900 KB Output is correct
3 Correct 10 ms 55900 KB Output is correct
4 Correct 10 ms 55900 KB Output is correct
5 Correct 8 ms 55900 KB Output is correct
6 Correct 9 ms 55900 KB Output is correct
7 Correct 9 ms 56112 KB Output is correct
8 Correct 11 ms 55900 KB Output is correct
9 Correct 10 ms 55900 KB Output is correct
10 Correct 84 ms 61828 KB Output is correct
11 Correct 98 ms 63136 KB Output is correct
12 Correct 108 ms 63216 KB Output is correct
13 Correct 105 ms 63632 KB Output is correct
14 Correct 89 ms 65932 KB Output is correct
15 Correct 83 ms 61892 KB Output is correct
16 Correct 204 ms 65108 KB Output is correct
17 Correct 186 ms 64884 KB Output is correct
18 Correct 204 ms 65340 KB Output is correct
19 Correct 234 ms 67696 KB Output is correct
20 Incorrect 246 ms 69108 KB Output isn't correct
21 Halted 0 ms 0 KB -