oj.uz

Submission #949859

# Submission time Handle Problem Language Result Execution time Memory
949859 2024-03-19T19:07:02 Z KiaRez Swapping Cities (APIO20_swap) C++17
6 / 100
 211 ms 69300 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) {
		while(m == n-1) fuck("you");
		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 9 ms 55896 KB Output is correct
2 Correct 8 ms 55900 KB Output is correct
3 Correct 8 ms 55900 KB Output is correct
4 Correct 9 ms 55900 KB Output is correct
5 Correct 9 ms 56104 KB Output is correct
6 Correct 9 ms 55900 KB Output is correct
7 Correct 9 ms 55900 KB Output is correct
8 Correct 9 ms 55900 KB Output is correct
9 Correct 72 ms 61880 KB Output is correct
10 Correct 102 ms 63324 KB Output is correct
11 Correct 97 ms 63064 KB Output is correct
12 Correct 105 ms 63668 KB Output is correct
13 Correct 87 ms 65968 KB Output is correct
14 Correct 103 ms 61896 KB Output is correct
15 Correct 188 ms 65108 KB Output is correct
16 Correct 192 ms 64836 KB Output is correct
17 Correct 191 ms 65324 KB Output is correct
18 Correct 211 ms 67700 KB Output is correct
19 Correct 85 ms 60624 KB Output is correct
20 Correct 189 ms 66340 KB Output is correct
21 Correct 199 ms 66296 KB Output is correct
22 Correct 209 ms 66864 KB Output is correct
23 Correct 207 ms 69116 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 55896 KB Output is correct
2 Correct 8 ms 55900 KB Output is correct
3 Incorrect 183 ms 69300 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 55896 KB Output is correct
2 Correct 8 ms 55900 KB Output is correct
3 Correct 8 ms 55900 KB Output is correct
4 Correct 9 ms 55900 KB Output is correct
5 Correct 9 ms 56104 KB Output is correct
6 Correct 9 ms 55900 KB Output is correct
7 Correct 9 ms 55900 KB Output is correct
8 Correct 9 ms 55900 KB Output is correct
9 Correct 8 ms 55900 KB Output is correct
10 Incorrect 9 ms 56056 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 9 ms 55896 KB Output is correct
3 Correct 8 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 56104 KB Output is correct
7 Correct 9 ms 55900 KB Output is correct
8 Correct 9 ms 55900 KB Output is correct
9 Correct 9 ms 55900 KB Output is correct
10 Correct 72 ms 61880 KB Output is correct
11 Correct 102 ms 63324 KB Output is correct
12 Correct 97 ms 63064 KB Output is correct
13 Correct 105 ms 63668 KB Output is correct
14 Correct 87 ms 65968 KB Output is correct
15 Incorrect 9 ms 56056 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 55896 KB Output is correct
2 Correct 8 ms 55900 KB Output is correct
3 Correct 8 ms 55900 KB Output is correct
4 Correct 9 ms 55900 KB Output is correct
5 Correct 9 ms 56104 KB Output is correct
6 Correct 9 ms 55900 KB Output is correct
7 Correct 9 ms 55900 KB Output is correct
8 Correct 9 ms 55900 KB Output is correct
9 Correct 72 ms 61880 KB Output is correct
10 Correct 102 ms 63324 KB Output is correct
11 Correct 97 ms 63064 KB Output is correct
12 Correct 105 ms 63668 KB Output is correct
13 Correct 87 ms 65968 KB Output is correct
14 Correct 103 ms 61896 KB Output is correct
15 Correct 188 ms 65108 KB Output is correct
16 Correct 192 ms 64836 KB Output is correct
17 Correct 191 ms 65324 KB Output is correct
18 Correct 211 ms 67700 KB Output is correct
19 Incorrect 183 ms 69300 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 9 ms 55896 KB Output is correct
3 Correct 8 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 56104 KB Output is correct
7 Correct 9 ms 55900 KB Output is correct
8 Correct 9 ms 55900 KB Output is correct
9 Correct 9 ms 55900 KB Output is correct
10 Correct 72 ms 61880 KB Output is correct
11 Correct 102 ms 63324 KB Output is correct
12 Correct 97 ms 63064 KB Output is correct
13 Correct 105 ms 63668 KB Output is correct
14 Correct 87 ms 65968 KB Output is correct
15 Correct 103 ms 61896 KB Output is correct
16 Correct 188 ms 65108 KB Output is correct
17 Correct 192 ms 64836 KB Output is correct
18 Correct 191 ms 65324 KB Output is correct
19 Correct 211 ms 67700 KB Output is correct
20 Incorrect 183 ms 69300 KB Output isn't correct
21 Halted 0 ms 0 KB -