oj.uz

Submission #949853

# Submission time Handle Problem Language Result Execution time Memory
949853 2024-03-19T18:59:03 Z KiaRez Swapping Cities (APIO20_swap) C++17
6 / 100
 311 ms 110636 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[lg][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[0][cnd[v]] = min(mx[0][cnd[v]], w);
		return;
	}

	tree[cnt].pb(cnd[v]); tree[cnt].pb(cnd[u]);
	ok[v] |= ok[u];
	if(ok[v] == 1) mx[0][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);
	for(int i=1; i<lg; i++) {
		par[i][v] = par[i-1][par[i-1][v]];
		if(par[i][v] == 0) par[i][v] = cnd[1];
		mx[i][v] = min(mx[i-1][v], mx[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});
	}
	for(int i=0; i<lg; i++) fill(mx[i], mx[i]+2*n+2, (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[lg-1][lca] == 2e9) return -1;
	return mx[lg-1][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 35 ms 92756 KB Output is correct
2 Correct 12 ms 92760 KB Output is correct
3 Correct 12 ms 92764 KB Output is correct
4 Correct 13 ms 92764 KB Output is correct
5 Correct 12 ms 92896 KB Output is correct
6 Correct 14 ms 93016 KB Output is correct
7 Correct 13 ms 93020 KB Output is correct
8 Correct 13 ms 93020 KB Output is correct
9 Correct 136 ms 99012 KB Output is correct
10 Correct 170 ms 100512 KB Output is correct
11 Correct 163 ms 100396 KB Output is correct
12 Correct 178 ms 101060 KB Output is correct
13 Correct 153 ms 103108 KB Output is correct
14 Correct 139 ms 99012 KB Output is correct
15 Correct 270 ms 102364 KB Output is correct
16 Correct 252 ms 102004 KB Output is correct
17 Correct 272 ms 102524 KB Output is correct
18 Correct 311 ms 104752 KB Output is correct
19 Correct 82 ms 97452 KB Output is correct
20 Correct 264 ms 107848 KB Output is correct
21 Correct 277 ms 107648 KB Output is correct
22 Correct 278 ms 108232 KB Output is correct
23 Correct 281 ms 110636 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 92756 KB Output is correct
2 Correct 12 ms 92760 KB Output is correct
3 Incorrect 247 ms 106600 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 92756 KB Output is correct
2 Correct 12 ms 92760 KB Output is correct
3 Correct 12 ms 92764 KB Output is correct
4 Correct 13 ms 92764 KB Output is correct
5 Correct 12 ms 92896 KB Output is correct
6 Correct 14 ms 93016 KB Output is correct
7 Correct 13 ms 93020 KB Output is correct
8 Correct 13 ms 93020 KB Output is correct
9 Correct 12 ms 92932 KB Output is correct
10 Incorrect 12 ms 93020 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 92932 KB Output is correct
2 Correct 35 ms 92756 KB Output is correct
3 Correct 12 ms 92760 KB Output is correct
4 Correct 12 ms 92764 KB Output is correct
5 Correct 13 ms 92764 KB Output is correct
6 Correct 12 ms 92896 KB Output is correct
7 Correct 14 ms 93016 KB Output is correct
8 Correct 13 ms 93020 KB Output is correct
9 Correct 13 ms 93020 KB Output is correct
10 Correct 136 ms 99012 KB Output is correct
11 Correct 170 ms 100512 KB Output is correct
12 Correct 163 ms 100396 KB Output is correct
13 Correct 178 ms 101060 KB Output is correct
14 Correct 153 ms 103108 KB Output is correct
15 Incorrect 12 ms 93020 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 92756 KB Output is correct
2 Correct 12 ms 92760 KB Output is correct
3 Correct 12 ms 92764 KB Output is correct
4 Correct 13 ms 92764 KB Output is correct
5 Correct 12 ms 92896 KB Output is correct
6 Correct 14 ms 93016 KB Output is correct
7 Correct 13 ms 93020 KB Output is correct
8 Correct 13 ms 93020 KB Output is correct
9 Correct 136 ms 99012 KB Output is correct
10 Correct 170 ms 100512 KB Output is correct
11 Correct 163 ms 100396 KB Output is correct
12 Correct 178 ms 101060 KB Output is correct
13 Correct 153 ms 103108 KB Output is correct
14 Correct 139 ms 99012 KB Output is correct
15 Correct 270 ms 102364 KB Output is correct
16 Correct 252 ms 102004 KB Output is correct
17 Correct 272 ms 102524 KB Output is correct
18 Correct 311 ms 104752 KB Output is correct
19 Incorrect 247 ms 106600 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 92932 KB Output is correct
2 Correct 35 ms 92756 KB Output is correct
3 Correct 12 ms 92760 KB Output is correct
4 Correct 12 ms 92764 KB Output is correct
5 Correct 13 ms 92764 KB Output is correct
6 Correct 12 ms 92896 KB Output is correct
7 Correct 14 ms 93016 KB Output is correct
8 Correct 13 ms 93020 KB Output is correct
9 Correct 13 ms 93020 KB Output is correct
10 Correct 136 ms 99012 KB Output is correct
11 Correct 170 ms 100512 KB Output is correct
12 Correct 163 ms 100396 KB Output is correct
13 Correct 178 ms 101060 KB Output is correct
14 Correct 153 ms 103108 KB Output is correct
15 Correct 139 ms 99012 KB Output is correct
16 Correct 270 ms 102364 KB Output is correct
17 Correct 252 ms 102004 KB Output is correct
18 Correct 272 ms 102524 KB Output is correct
19 Correct 311 ms 104752 KB Output is correct
20 Incorrect 247 ms 106600 KB Output isn't correct
21 Halted 0 ms 0 KB -