oj.uz

Submission #949850

# Submission time Handle Problem Language Result Execution time Memory
949850 2024-03-19T18:51:24 Z KiaRez Swapping Cities (APIO20_swap) C++17
0 / 100
 227 ms 76108 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<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[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 9 ms 60248 KB Output is correct
2 Correct 8 ms 59996 KB Output is correct
3 Correct 9 ms 59996 KB Output is correct
4 Correct 11 ms 31388 KB Output is correct
5 Correct 11 ms 16092 KB Output is correct
6 Correct 9 ms 59996 KB Output is correct
7 Correct 8 ms 16220 KB Output is correct
8 Correct 9 ms 16220 KB Output is correct
9 Correct 44 ms 66520 KB Output is correct
10 Correct 49 ms 68036 KB Output is correct
11 Correct 52 ms 68240 KB Output is correct
12 Correct 55 ms 68040 KB Output is correct
13 Correct 54 ms 68956 KB Output is correct
14 Correct 48 ms 66760 KB Output is correct
15 Correct 110 ms 70904 KB Output is correct
16 Correct 104 ms 70492 KB Output is correct
17 Correct 110 ms 71404 KB Output is correct
18 Correct 135 ms 73004 KB Output is correct
19 Incorrect 61 ms 64784 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 60248 KB Output is correct
2 Correct 8 ms 59996 KB Output is correct
3 Incorrect 227 ms 76108 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 60248 KB Output is correct
2 Correct 8 ms 59996 KB Output is correct
3 Correct 9 ms 59996 KB Output is correct
4 Correct 11 ms 31388 KB Output is correct
5 Correct 11 ms 16092 KB Output is correct
6 Correct 9 ms 59996 KB Output is correct
7 Correct 8 ms 16220 KB Output is correct
8 Correct 9 ms 16220 KB Output is correct
9 Correct 9 ms 59992 KB Output is correct
10 Incorrect 9 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 9 ms 60248 KB Output is correct
3 Correct 8 ms 59996 KB Output is correct
4 Correct 9 ms 59996 KB Output is correct
5 Correct 11 ms 31388 KB Output is correct
6 Correct 11 ms 16092 KB Output is correct
7 Correct 9 ms 59996 KB Output is correct
8 Correct 8 ms 16220 KB Output is correct
9 Correct 9 ms 16220 KB Output is correct
10 Correct 44 ms 66520 KB Output is correct
11 Correct 49 ms 68036 KB Output is correct
12 Correct 52 ms 68240 KB Output is correct
13 Correct 55 ms 68040 KB Output is correct
14 Correct 54 ms 68956 KB Output is correct
15 Incorrect 9 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 9 ms 60248 KB Output is correct
2 Correct 8 ms 59996 KB Output is correct
3 Correct 9 ms 59996 KB Output is correct
4 Correct 11 ms 31388 KB Output is correct
5 Correct 11 ms 16092 KB Output is correct
6 Correct 9 ms 59996 KB Output is correct
7 Correct 8 ms 16220 KB Output is correct
8 Correct 9 ms 16220 KB Output is correct
9 Correct 44 ms 66520 KB Output is correct
10 Correct 49 ms 68036 KB Output is correct
11 Correct 52 ms 68240 KB Output is correct
12 Correct 55 ms 68040 KB Output is correct
13 Correct 54 ms 68956 KB Output is correct
14 Correct 48 ms 66760 KB Output is correct
15 Correct 110 ms 70904 KB Output is correct
16 Correct 104 ms 70492 KB Output is correct
17 Correct 110 ms 71404 KB Output is correct
18 Correct 135 ms 73004 KB Output is correct
19 Incorrect 227 ms 76108 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 9 ms 60248 KB Output is correct
3 Correct 8 ms 59996 KB Output is correct
4 Correct 9 ms 59996 KB Output is correct
5 Correct 11 ms 31388 KB Output is correct
6 Correct 11 ms 16092 KB Output is correct
7 Correct 9 ms 59996 KB Output is correct
8 Correct 8 ms 16220 KB Output is correct
9 Correct 9 ms 16220 KB Output is correct
10 Correct 44 ms 66520 KB Output is correct
11 Correct 49 ms 68036 KB Output is correct
12 Correct 52 ms 68240 KB Output is correct
13 Correct 55 ms 68040 KB Output is correct
14 Correct 54 ms 68956 KB Output is correct
15 Correct 48 ms 66760 KB Output is correct
16 Correct 110 ms 70904 KB Output is correct
17 Correct 104 ms 70492 KB Output is correct
18 Correct 110 ms 71404 KB Output is correct
19 Correct 135 ms 73004 KB Output is correct
20 Incorrect 227 ms 76108 KB Output isn't correct
21 Halted 0 ms 0 KB -