oj.uz

Submission #949851

# Submission time Handle Problem Language Result Execution time Memory
949851 2024-03-19T18:53:58 Z KiaRez Swapping Cities (APIO20_swap) C++17
0 / 100
 280 ms 118508 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[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 15 ms 105308 KB Output is correct
2 Correct 15 ms 105052 KB Output is correct
3 Correct 15 ms 105048 KB Output is correct
4 Correct 15 ms 105052 KB Output is correct
5 Correct 15 ms 105308 KB Output is correct
6 Correct 15 ms 105308 KB Output is correct
7 Correct 15 ms 105308 KB Output is correct
8 Correct 15 ms 105308 KB Output is correct
9 Correct 48 ms 110536 KB Output is correct
10 Correct 56 ms 111668 KB Output is correct
11 Correct 60 ms 111972 KB Output is correct
12 Correct 57 ms 111828 KB Output is correct
13 Correct 58 ms 112584 KB Output is correct
14 Correct 54 ms 110532 KB Output is correct
15 Correct 112 ms 113576 KB Output is correct
16 Correct 111 ms 113272 KB Output is correct
17 Correct 114 ms 113672 KB Output is correct
18 Correct 143 ms 114984 KB Output is correct
19 Incorrect 64 ms 108624 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 105308 KB Output is correct
2 Correct 15 ms 105052 KB Output is correct
3 Incorrect 280 ms 118508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 105308 KB Output is correct
2 Correct 15 ms 105052 KB Output is correct
3 Correct 15 ms 105048 KB Output is correct
4 Correct 15 ms 105052 KB Output is correct
5 Correct 15 ms 105308 KB Output is correct
6 Correct 15 ms 105308 KB Output is correct
7 Correct 15 ms 105308 KB Output is correct
8 Correct 15 ms 105308 KB Output is correct
9 Correct 14 ms 105048 KB Output is correct
10 Incorrect 15 ms 105308 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 105048 KB Output is correct
2 Correct 15 ms 105308 KB Output is correct
3 Correct 15 ms 105052 KB Output is correct
4 Correct 15 ms 105048 KB Output is correct
5 Correct 15 ms 105052 KB Output is correct
6 Correct 15 ms 105308 KB Output is correct
7 Correct 15 ms 105308 KB Output is correct
8 Correct 15 ms 105308 KB Output is correct
9 Correct 15 ms 105308 KB Output is correct
10 Correct 48 ms 110536 KB Output is correct
11 Correct 56 ms 111668 KB Output is correct
12 Correct 60 ms 111972 KB Output is correct
13 Correct 57 ms 111828 KB Output is correct
14 Correct 58 ms 112584 KB Output is correct
15 Incorrect 15 ms 105308 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 105308 KB Output is correct
2 Correct 15 ms 105052 KB Output is correct
3 Correct 15 ms 105048 KB Output is correct
4 Correct 15 ms 105052 KB Output is correct
5 Correct 15 ms 105308 KB Output is correct
6 Correct 15 ms 105308 KB Output is correct
7 Correct 15 ms 105308 KB Output is correct
8 Correct 15 ms 105308 KB Output is correct
9 Correct 48 ms 110536 KB Output is correct
10 Correct 56 ms 111668 KB Output is correct
11 Correct 60 ms 111972 KB Output is correct
12 Correct 57 ms 111828 KB Output is correct
13 Correct 58 ms 112584 KB Output is correct
14 Correct 54 ms 110532 KB Output is correct
15 Correct 112 ms 113576 KB Output is correct
16 Correct 111 ms 113272 KB Output is correct
17 Correct 114 ms 113672 KB Output is correct
18 Correct 143 ms 114984 KB Output is correct
19 Incorrect 280 ms 118508 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 105048 KB Output is correct
2 Correct 15 ms 105308 KB Output is correct
3 Correct 15 ms 105052 KB Output is correct
4 Correct 15 ms 105048 KB Output is correct
5 Correct 15 ms 105052 KB Output is correct
6 Correct 15 ms 105308 KB Output is correct
7 Correct 15 ms 105308 KB Output is correct
8 Correct 15 ms 105308 KB Output is correct
9 Correct 15 ms 105308 KB Output is correct
10 Correct 48 ms 110536 KB Output is correct
11 Correct 56 ms 111668 KB Output is correct
12 Correct 60 ms 111972 KB Output is correct
13 Correct 57 ms 111828 KB Output is correct
14 Correct 58 ms 112584 KB Output is correct
15 Correct 54 ms 110532 KB Output is correct
16 Correct 112 ms 113576 KB Output is correct
17 Correct 111 ms 113272 KB Output is correct
18 Correct 114 ms 113672 KB Output is correct
19 Correct 143 ms 114984 KB Output is correct
20 Incorrect 280 ms 118508 KB Output isn't correct
21 Halted 0 ms 0 KB -