oj.uz

Submission #949843

# Submission time Handle Problem Language Result Execution time Memory
949843 2024-03-19T18:39:00 Z KiaRez Swapping Cities (APIO20_swap) C++17
0 / 100
 248 ms 75816 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(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 8 ms 59996 KB Output is correct
2 Correct 9 ms 60044 KB Output is correct
3 Correct 9 ms 59996 KB Output is correct
4 Correct 9 ms 59996 KB Output is correct
5 Correct 9 ms 59996 KB Output is correct
6 Correct 9 ms 59996 KB Output is correct
7 Correct 9 ms 60212 KB Output is correct
8 Correct 9 ms 60252 KB Output is correct
9 Correct 43 ms 67016 KB Output is correct
10 Correct 47 ms 68552 KB Output is correct
11 Correct 48 ms 68984 KB Output is correct
12 Correct 49 ms 68700 KB Output is correct
13 Correct 50 ms 69788 KB Output is correct
14 Correct 53 ms 67468 KB Output is correct
15 Correct 106 ms 72784 KB Output is correct
16 Correct 104 ms 72312 KB Output is correct
17 Correct 106 ms 73224 KB Output is correct
18 Correct 135 ms 75028 KB Output is correct
19 Incorrect 58 ms 65280 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 59996 KB Output is correct
2 Correct 9 ms 60044 KB Output is correct
3 Incorrect 248 ms 75816 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 59996 KB Output is correct
2 Correct 9 ms 60044 KB Output is correct
3 Correct 9 ms 59996 KB Output is correct
4 Correct 9 ms 59996 KB Output is correct
5 Correct 9 ms 59996 KB Output is correct
6 Correct 9 ms 59996 KB Output is correct
7 Correct 9 ms 60212 KB Output is correct
8 Correct 9 ms 60252 KB Output is correct
9 Correct 9 ms 59996 KB Output is correct
10 Incorrect 10 ms 60184 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 59996 KB Output is correct
2 Correct 8 ms 59996 KB Output is correct
3 Correct 9 ms 60044 KB Output is correct
4 Correct 9 ms 59996 KB Output is correct
5 Correct 9 ms 59996 KB Output is correct
6 Correct 9 ms 59996 KB Output is correct
7 Correct 9 ms 59996 KB Output is correct
8 Correct 9 ms 60212 KB Output is correct
9 Correct 9 ms 60252 KB Output is correct
10 Correct 43 ms 67016 KB Output is correct
11 Correct 47 ms 68552 KB Output is correct
12 Correct 48 ms 68984 KB Output is correct
13 Correct 49 ms 68700 KB Output is correct
14 Correct 50 ms 69788 KB Output is correct
15 Incorrect 10 ms 60184 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 59996 KB Output is correct
2 Correct 9 ms 60044 KB Output is correct
3 Correct 9 ms 59996 KB Output is correct
4 Correct 9 ms 59996 KB Output is correct
5 Correct 9 ms 59996 KB Output is correct
6 Correct 9 ms 59996 KB Output is correct
7 Correct 9 ms 60212 KB Output is correct
8 Correct 9 ms 60252 KB Output is correct
9 Correct 43 ms 67016 KB Output is correct
10 Correct 47 ms 68552 KB Output is correct
11 Correct 48 ms 68984 KB Output is correct
12 Correct 49 ms 68700 KB Output is correct
13 Correct 50 ms 69788 KB Output is correct
14 Correct 53 ms 67468 KB Output is correct
15 Correct 106 ms 72784 KB Output is correct
16 Correct 104 ms 72312 KB Output is correct
17 Correct 106 ms 73224 KB Output is correct
18 Correct 135 ms 75028 KB Output is correct
19 Incorrect 248 ms 75816 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 59996 KB Output is correct
2 Correct 8 ms 59996 KB Output is correct
3 Correct 9 ms 60044 KB Output is correct
4 Correct 9 ms 59996 KB Output is correct
5 Correct 9 ms 59996 KB Output is correct
6 Correct 9 ms 59996 KB Output is correct
7 Correct 9 ms 59996 KB Output is correct
8 Correct 9 ms 60212 KB Output is correct
9 Correct 9 ms 60252 KB Output is correct
10 Correct 43 ms 67016 KB Output is correct
11 Correct 47 ms 68552 KB Output is correct
12 Correct 48 ms 68984 KB Output is correct
13 Correct 49 ms 68700 KB Output is correct
14 Correct 50 ms 69788 KB Output is correct
15 Correct 53 ms 67468 KB Output is correct
16 Correct 106 ms 72784 KB Output is correct
17 Correct 104 ms 72312 KB Output is correct
18 Correct 106 ms 73224 KB Output is correct
19 Correct 135 ms 75028 KB Output is correct
20 Incorrect 248 ms 75816 KB Output isn't correct
21 Halted 0 ms 0 KB -