oj.uz

답안 #949844

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
949844 2024-03-19T18:40:06 Z KiaRez 자매 도시 (APIO20_swap) C++17
0 / 100
 238 ms 118284 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<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

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 105048 KB Output is correct
2 Correct 15 ms 105048 KB Output is correct
3 Correct 14 ms 105052 KB Output is correct
4 Correct 17 ms 105176 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 105304 KB Output is correct
8 Correct 15 ms 105308 KB Output is correct
9 Correct 47 ms 110552 KB Output is correct
10 Correct 53 ms 111560 KB Output is correct
11 Correct 53 ms 111820 KB Output is correct
12 Correct 56 ms 111820 KB Output is correct
13 Correct 56 ms 112840 KB Output is correct
14 Correct 55 ms 110652 KB Output is correct
15 Correct 110 ms 113692 KB Output is correct
16 Correct 117 ms 113192 KB Output is correct
17 Correct 116 ms 113964 KB Output is correct
18 Correct 139 ms 114988 KB Output is correct
19 Incorrect 68 ms 108352 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 105048 KB Output is correct
2 Correct 15 ms 105048 KB Output is correct
3 Incorrect 238 ms 118284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 105048 KB Output is correct
2 Correct 15 ms 105048 KB Output is correct
3 Correct 14 ms 105052 KB Output is correct
4 Correct 17 ms 105176 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 105304 KB Output is correct
8 Correct 15 ms 105308 KB Output is correct
9 Correct 16 ms 105048 KB Output is correct
10 Incorrect 16 ms 105140 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 105048 KB Output is correct
2 Correct 23 ms 105048 KB Output is correct
3 Correct 15 ms 105048 KB Output is correct
4 Correct 14 ms 105052 KB Output is correct
5 Correct 17 ms 105176 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 105304 KB Output is correct
9 Correct 15 ms 105308 KB Output is correct
10 Correct 47 ms 110552 KB Output is correct
11 Correct 53 ms 111560 KB Output is correct
12 Correct 53 ms 111820 KB Output is correct
13 Correct 56 ms 111820 KB Output is correct
14 Correct 56 ms 112840 KB Output is correct
15 Incorrect 16 ms 105140 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 105048 KB Output is correct
2 Correct 15 ms 105048 KB Output is correct
3 Correct 14 ms 105052 KB Output is correct
4 Correct 17 ms 105176 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 105304 KB Output is correct
8 Correct 15 ms 105308 KB Output is correct
9 Correct 47 ms 110552 KB Output is correct
10 Correct 53 ms 111560 KB Output is correct
11 Correct 53 ms 111820 KB Output is correct
12 Correct 56 ms 111820 KB Output is correct
13 Correct 56 ms 112840 KB Output is correct
14 Correct 55 ms 110652 KB Output is correct
15 Correct 110 ms 113692 KB Output is correct
16 Correct 117 ms 113192 KB Output is correct
17 Correct 116 ms 113964 KB Output is correct
18 Correct 139 ms 114988 KB Output is correct
19 Incorrect 238 ms 118284 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 105048 KB Output is correct
2 Correct 23 ms 105048 KB Output is correct
3 Correct 15 ms 105048 KB Output is correct
4 Correct 14 ms 105052 KB Output is correct
5 Correct 17 ms 105176 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 105304 KB Output is correct
9 Correct 15 ms 105308 KB Output is correct
10 Correct 47 ms 110552 KB Output is correct
11 Correct 53 ms 111560 KB Output is correct
12 Correct 53 ms 111820 KB Output is correct
13 Correct 56 ms 111820 KB Output is correct
14 Correct 56 ms 112840 KB Output is correct
15 Correct 55 ms 110652 KB Output is correct
16 Correct 110 ms 113692 KB Output is correct
17 Correct 117 ms 113192 KB Output is correct
18 Correct 116 ms 113964 KB Output is correct
19 Correct 139 ms 114988 KB Output is correct
20 Incorrect 238 ms 118284 KB Output isn't correct
21 Halted 0 ms 0 KB -