oj.uz

Submission #949862

# Submission time Handle Problem Language Result Execution time Memory
949862 2024-03-19T19:09:32 Z KiaRez Swapping Cities (APIO20_swap) C++17
6 / 100
 209 ms 68192 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(m==n-1) return -1;
	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 11 ms 55900 KB Output is correct
2 Correct 9 ms 55900 KB Output is correct
3 Correct 8 ms 55900 KB Output is correct
4 Correct 8 ms 55900 KB Output is correct
5 Correct 10 ms 56064 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 56076 KB Output is correct
9 Correct 71 ms 61888 KB Output is correct
10 Correct 95 ms 63184 KB Output is correct
11 Correct 100 ms 63176 KB Output is correct
12 Correct 99 ms 63432 KB Output is correct
13 Correct 84 ms 65220 KB Output is correct
14 Correct 83 ms 61892 KB Output is correct
15 Correct 186 ms 65208 KB Output is correct
16 Correct 199 ms 65192 KB Output is correct
17 Correct 203 ms 65384 KB Output is correct
18 Correct 203 ms 66864 KB Output is correct
19 Correct 73 ms 60496 KB Output is correct
20 Correct 182 ms 66116 KB Output is correct
21 Correct 182 ms 66320 KB Output is correct
22 Correct 203 ms 66880 KB Output is correct
23 Correct 209 ms 68192 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 55900 KB Output is correct
2 Correct 9 ms 55900 KB Output is correct
3 Incorrect 169 ms 67716 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 55900 KB Output is correct
2 Correct 9 ms 55900 KB Output is correct
3 Correct 8 ms 55900 KB Output is correct
4 Correct 8 ms 55900 KB Output is correct
5 Correct 10 ms 56064 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 56076 KB Output is correct
9 Correct 9 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 9 ms 55900 KB Output is correct
2 Correct 11 ms 55900 KB Output is correct
3 Correct 9 ms 55900 KB Output is correct
4 Correct 8 ms 55900 KB Output is correct
5 Correct 8 ms 55900 KB Output is correct
6 Correct 10 ms 56064 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 56076 KB Output is correct
10 Correct 71 ms 61888 KB Output is correct
11 Correct 95 ms 63184 KB Output is correct
12 Correct 100 ms 63176 KB Output is correct
13 Correct 99 ms 63432 KB Output is correct
14 Correct 84 ms 65220 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 11 ms 55900 KB Output is correct
2 Correct 9 ms 55900 KB Output is correct
3 Correct 8 ms 55900 KB Output is correct
4 Correct 8 ms 55900 KB Output is correct
5 Correct 10 ms 56064 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 56076 KB Output is correct
9 Correct 71 ms 61888 KB Output is correct
10 Correct 95 ms 63184 KB Output is correct
11 Correct 100 ms 63176 KB Output is correct
12 Correct 99 ms 63432 KB Output is correct
13 Correct 84 ms 65220 KB Output is correct
14 Correct 83 ms 61892 KB Output is correct
15 Correct 186 ms 65208 KB Output is correct
16 Correct 199 ms 65192 KB Output is correct
17 Correct 203 ms 65384 KB Output is correct
18 Correct 203 ms 66864 KB Output is correct
19 Incorrect 169 ms 67716 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 55900 KB Output is correct
2 Correct 11 ms 55900 KB Output is correct
3 Correct 9 ms 55900 KB Output is correct
4 Correct 8 ms 55900 KB Output is correct
5 Correct 8 ms 55900 KB Output is correct
6 Correct 10 ms 56064 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 56076 KB Output is correct
10 Correct 71 ms 61888 KB Output is correct
11 Correct 95 ms 63184 KB Output is correct
12 Correct 100 ms 63176 KB Output is correct
13 Correct 99 ms 63432 KB Output is correct
14 Correct 84 ms 65220 KB Output is correct
15 Correct 83 ms 61892 KB Output is correct
16 Correct 186 ms 65208 KB Output is correct
17 Correct 199 ms 65192 KB Output is correct
18 Correct 203 ms 65384 KB Output is correct
19 Correct 203 ms 66864 KB Output is correct
20 Incorrect 169 ms 67716 KB Output isn't correct
21 Halted 0 ms 0 KB -