oj.uz

Submission #949855

# Submission time Handle Problem Language Result Execution time Memory
949855 2024-03-19T19:00:19 Z KiaRez Swapping Cities (APIO20_swap) C++17
6 / 100
 329 ms 109504 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[getPar(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 16 ms 93016 KB Output is correct
2 Correct 12 ms 92760 KB Output is correct
3 Correct 12 ms 93016 KB Output is correct
4 Correct 12 ms 92928 KB Output is correct
5 Correct 13 ms 92856 KB Output is correct
6 Correct 14 ms 93044 KB Output is correct
7 Correct 12 ms 92876 KB Output is correct
8 Correct 13 ms 93020 KB Output is correct
9 Correct 146 ms 98920 KB Output is correct
10 Correct 178 ms 100484 KB Output is correct
11 Correct 170 ms 100440 KB Output is correct
12 Correct 187 ms 100844 KB Output is correct
13 Correct 141 ms 104644 KB Output is correct
14 Correct 137 ms 99012 KB Output is correct
15 Correct 256 ms 102248 KB Output is correct
16 Correct 256 ms 102164 KB Output is correct
17 Correct 265 ms 102500 KB Output is correct
18 Correct 283 ms 106544 KB Output is correct
19 Correct 77 ms 97620 KB Output is correct
20 Correct 260 ms 103288 KB Output is correct
21 Correct 249 ms 103432 KB Output is correct
22 Correct 296 ms 103816 KB Output is correct
23 Correct 329 ms 107724 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 93016 KB Output is correct
2 Correct 12 ms 92760 KB Output is correct
3 Incorrect 268 ms 109504 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 93016 KB Output is correct
2 Correct 12 ms 92760 KB Output is correct
3 Correct 12 ms 93016 KB Output is correct
4 Correct 12 ms 92928 KB Output is correct
5 Correct 13 ms 92856 KB Output is correct
6 Correct 14 ms 93044 KB Output is correct
7 Correct 12 ms 92876 KB Output is correct
8 Correct 13 ms 93020 KB Output is correct
9 Correct 12 ms 92760 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 92760 KB Output is correct
2 Correct 16 ms 93016 KB Output is correct
3 Correct 12 ms 92760 KB Output is correct
4 Correct 12 ms 93016 KB Output is correct
5 Correct 12 ms 92928 KB Output is correct
6 Correct 13 ms 92856 KB Output is correct
7 Correct 14 ms 93044 KB Output is correct
8 Correct 12 ms 92876 KB Output is correct
9 Correct 13 ms 93020 KB Output is correct
10 Correct 146 ms 98920 KB Output is correct
11 Correct 178 ms 100484 KB Output is correct
12 Correct 170 ms 100440 KB Output is correct
13 Correct 187 ms 100844 KB Output is correct
14 Correct 141 ms 104644 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 16 ms 93016 KB Output is correct
2 Correct 12 ms 92760 KB Output is correct
3 Correct 12 ms 93016 KB Output is correct
4 Correct 12 ms 92928 KB Output is correct
5 Correct 13 ms 92856 KB Output is correct
6 Correct 14 ms 93044 KB Output is correct
7 Correct 12 ms 92876 KB Output is correct
8 Correct 13 ms 93020 KB Output is correct
9 Correct 146 ms 98920 KB Output is correct
10 Correct 178 ms 100484 KB Output is correct
11 Correct 170 ms 100440 KB Output is correct
12 Correct 187 ms 100844 KB Output is correct
13 Correct 141 ms 104644 KB Output is correct
14 Correct 137 ms 99012 KB Output is correct
15 Correct 256 ms 102248 KB Output is correct
16 Correct 256 ms 102164 KB Output is correct
17 Correct 265 ms 102500 KB Output is correct
18 Correct 283 ms 106544 KB Output is correct
19 Incorrect 268 ms 109504 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 92760 KB Output is correct
2 Correct 16 ms 93016 KB Output is correct
3 Correct 12 ms 92760 KB Output is correct
4 Correct 12 ms 93016 KB Output is correct
5 Correct 12 ms 92928 KB Output is correct
6 Correct 13 ms 92856 KB Output is correct
7 Correct 14 ms 93044 KB Output is correct
8 Correct 12 ms 92876 KB Output is correct
9 Correct 13 ms 93020 KB Output is correct
10 Correct 146 ms 98920 KB Output is correct
11 Correct 178 ms 100484 KB Output is correct
12 Correct 170 ms 100440 KB Output is correct
13 Correct 187 ms 100844 KB Output is correct
14 Correct 141 ms 104644 KB Output is correct
15 Correct 137 ms 99012 KB Output is correct
16 Correct 256 ms 102248 KB Output is correct
17 Correct 256 ms 102164 KB Output is correct
18 Correct 265 ms 102500 KB Output is correct
19 Correct 283 ms 106544 KB Output is correct
20 Incorrect 268 ms 109504 KB Output isn't correct
21 Halted 0 ms 0 KB -