oj.uz

답안 #949850

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
949850 2024-03-19T18:51:24 Z KiaRez 자매 도시 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -