oj.uz

Submission #949848

# Submission time Handle Problem Language Result Execution time Memory
949848 2024-03-19T18:48:41 Z KiaRez Swapping Cities (APIO20_swap) C++17
0 / 100
 198 ms 73832 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 = 3e5+23, lg = 19;
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> adj[N], 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<N; i++) mx[0][i] = 2e9, cnd[i] = i;
	sort(all(e));
	for(auto it : e) {
		merge(V[it.S], U[it.S], it.F);
	}
	dfs_init(cnd[1]);
}

int getMinimumFuelCapacity(int v, int u) {
	v++, u++;
	int lca = LCA(v, u);
	if(mx[lg-1][lca] == 2e9 && m > n-1) return -1;
	if(m == n-1) 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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 59996 KB Output is correct
2 Correct 10 ms 59996 KB Output is correct
3 Correct 10 ms 59996 KB Output is correct
4 Correct 12 ms 59992 KB Output is correct
5 Correct 9 ms 59996 KB Output is correct
6 Correct 9 ms 60332 KB Output is correct
7 Correct 9 ms 59996 KB Output is correct
8 Correct 9 ms 59996 KB Output is correct
9 Correct 39 ms 65476 KB Output is correct
10 Correct 46 ms 66504 KB Output is correct
11 Correct 47 ms 67012 KB Output is correct
12 Correct 48 ms 66680 KB Output is correct
13 Correct 49 ms 67652 KB Output is correct
14 Correct 45 ms 65612 KB Output is correct
15 Correct 102 ms 68432 KB Output is correct
16 Correct 101 ms 68216 KB Output is correct
17 Correct 110 ms 68812 KB Output is correct
18 Correct 141 ms 70276 KB Output is correct
19 Incorrect 59 ms 63160 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 59996 KB Output is correct
2 Correct 10 ms 59996 KB Output is correct
3 Incorrect 198 ms 73832 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 59996 KB Output is correct
2 Correct 10 ms 59996 KB Output is correct
3 Correct 10 ms 59996 KB Output is correct
4 Correct 12 ms 59992 KB Output is correct
5 Correct 9 ms 59996 KB Output is correct
6 Correct 9 ms 60332 KB Output is correct
7 Correct 9 ms 59996 KB Output is correct
8 Correct 9 ms 59996 KB Output is correct
9 Correct 9 ms 59992 KB Output is correct
10 Incorrect 10 ms 59996 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 59992 KB Output is correct
2 Correct 13 ms 59996 KB Output is correct
3 Correct 10 ms 59996 KB Output is correct
4 Correct 10 ms 59996 KB Output is correct
5 Correct 12 ms 59992 KB Output is correct
6 Correct 9 ms 59996 KB Output is correct
7 Correct 9 ms 60332 KB Output is correct
8 Correct 9 ms 59996 KB Output is correct
9 Correct 9 ms 59996 KB Output is correct
10 Correct 39 ms 65476 KB Output is correct
11 Correct 46 ms 66504 KB Output is correct
12 Correct 47 ms 67012 KB Output is correct
13 Correct 48 ms 66680 KB Output is correct
14 Correct 49 ms 67652 KB Output is correct
15 Incorrect 10 ms 59996 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 59996 KB Output is correct
2 Correct 10 ms 59996 KB Output is correct
3 Correct 10 ms 59996 KB Output is correct
4 Correct 12 ms 59992 KB Output is correct
5 Correct 9 ms 59996 KB Output is correct
6 Correct 9 ms 60332 KB Output is correct
7 Correct 9 ms 59996 KB Output is correct
8 Correct 9 ms 59996 KB Output is correct
9 Correct 39 ms 65476 KB Output is correct
10 Correct 46 ms 66504 KB Output is correct
11 Correct 47 ms 67012 KB Output is correct
12 Correct 48 ms 66680 KB Output is correct
13 Correct 49 ms 67652 KB Output is correct
14 Correct 45 ms 65612 KB Output is correct
15 Correct 102 ms 68432 KB Output is correct
16 Correct 101 ms 68216 KB Output is correct
17 Correct 110 ms 68812 KB Output is correct
18 Correct 141 ms 70276 KB Output is correct
19 Incorrect 198 ms 73832 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 59992 KB Output is correct
2 Correct 13 ms 59996 KB Output is correct
3 Correct 10 ms 59996 KB Output is correct
4 Correct 10 ms 59996 KB Output is correct
5 Correct 12 ms 59992 KB Output is correct
6 Correct 9 ms 59996 KB Output is correct
7 Correct 9 ms 60332 KB Output is correct
8 Correct 9 ms 59996 KB Output is correct
9 Correct 9 ms 59996 KB Output is correct
10 Correct 39 ms 65476 KB Output is correct
11 Correct 46 ms 66504 KB Output is correct
12 Correct 47 ms 67012 KB Output is correct
13 Correct 48 ms 66680 KB Output is correct
14 Correct 49 ms 67652 KB Output is correct
15 Correct 45 ms 65612 KB Output is correct
16 Correct 102 ms 68432 KB Output is correct
17 Correct 101 ms 68216 KB Output is correct
18 Correct 110 ms 68812 KB Output is correct
19 Correct 141 ms 70276 KB Output is correct
20 Incorrect 198 ms 73832 KB Output isn't correct
21 Halted 0 ms 0 KB -