oj.uz

Submission #743659

# Submission time Handle Problem Language Result Execution time Memory
743659 2023-05-17T15:56:38 Z tolbi Swapping Cities (APIO20_swap) C++17
0 / 100
 901 ms 82092 KB 
#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& in, pair<X,Y> &pr) {return in>>pr.first>>pr.second;}
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr) {return os<<pr.first<<" "<<pr.second;}
template<typename X, typename Y> pair<X,Y> operator+(pair<X,Y> a, pair<X,Y> b) {pair<X,Y> c; c.first=a.first+b.first,c.second=a.second+b.second;return c;}
template<typename X, typename Y> pair<X,Y> operator-(pair<X,Y> a, pair<X,Y> b) {pair<X,Y> c; c.first=a.first-b.first,c.second=a.second-b.second;return c;}
template<typename X, typename Y> void operator+=(pair<X,Y> &a, pair<X,Y> b){a.first+=b.first,a.second+=b.second;}
template<typename X, typename Y> void operator-=(pair<X,Y> &a, pair<X,Y> b){a.first-=b.first,a.second-=b.second;}
template<typename X> istream& operator>>(istream& in, vector<X> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X> ostream& operator<<(ostream& os, vector<X> arr) {for(auto &it : arr) os<<it<<" "; return os;}
template<typename X, size_t Y> istream& operator>>(istream& in, array<X,Y> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> arr) {for(auto &it : arr) os<<it<<" "; return os;}
#define int long long
#define endl '\n'
#define vint(x) vector<int> x
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(),x.end())
#define sortrarr(x) sort(x.rbegin(),x.rend())
#define det(x) cout<<"NO\0YES"+x*3<<endl;
#define INF LONG_LONG_MAX
#define rev(x) reverse(x.begin(),x.end());
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define tol(bi) (1LL<<((int)(bi)))
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());


#include "swap.h"
vector<int> par;
vector<int> dep;
vector<vector<int>> st;
vector<vector<int>> mi;
vector<vector<int>> pa;
vector<int> val;
vector<int> c2;
vector<int> c3;
vector<int> up;
int LOG;
int find(int node){
	if (par[node]==node) return node;
	return par[node]=find(par[node]);
}
void init(int32_t N, int32_t M, vector<int32_t> U, vector<int32_t> V, vector<int32_t> W) {
	LOG = log2(N)+3;
	par.resize(N);
	dep.resize(N);
	val.resize(N,INF);
	c2.resize(N,INF);
	c3.resize(N,INF);
	up.resize(N,INF);
	st.resize(N,vector<int>(LOG,-1));
	mi.resize(N,vector<int>(LOG,INF));
	pa.resize(N,vector<int>(LOG,0));
	vector<pair<int,pair<int,int>>> ed(M);
	vector<vector<pair<int,int>>> arr(N);
	iota(par.begin(), par.end(), 0ll);
	for (int i = 0; i < M; i++){
		ed[i]={W[i],{U[i],V[i]}};
	}
	sortarr(ed);
	for (int i = 0; i < M; i++){
		int w = ed[i].first;
		int u = ed[i].second.first;
		int v = ed[i].second.second;
		if (find(u)==find(v)){
			val[u]=min(val[u],w);
			val[v]=min(val[v],w);
			continue;
		}
		arr[u].push_back({v,w});
		arr[v].push_back({u,w});
		u=find(u);
		v=find(v);
		if (ayahya()%2) swap(u,v);
		par[u]=v;
	}
	for (int i = 0; i < N; i++){
		sort(arr[i].begin(), arr[i].end(), [&](pair<int,int> a, pair<int,int> b){
			return a.second<b.second;
		});
	}
	auto dfs = [&](int node, int lnode, auto dfs)->void{
		int indi = 0;
		if (lnode==-1) dep[node]=0;
		else dep[node]=dep[lnode]+1;
		for (int i = 0; i < arr[node].size(); i++){
			if (arr[node][i].first==lnode) continue;
			st[arr[node][i].first][0]=node;
			pa[arr[node][i].first][0]=arr[node][i].second;
			indi++;
			if (indi==2){
				mi[node][0]=min(mi[node][0],arr[node][i].second);
				mi[node][0]=min(mi[node][0],val[node]);
				c2[node]=arr[node][i].second;
			}
			else if (indi==3){
				c3[node]=arr[node][i].second;
			}
			up[arr[node][i].first]=arr[node][i].second;
			dfs(arr[node][i].first,node,dfs);
		}
	};
	dfs(0,-1,dfs);
	for (int bit = 1; bit < LOG; bit++){
		for (int i = 0; i < N; i++){
			if (st[i][bit-1]==-1) continue;
			st[i][bit]=st[st[i][bit-1]][bit-1];
			mi[i][bit]=min(mi[i][bit-1],mi[st[i][bit-1]][bit-1]);
			pa[i][bit]=max(pa[i][bit-1],pa[st[i][bit-1]][bit-1]);
		}
	}
}
array<int,3> kthpar(int node, int k){
	array<int,3> ans={node,0,INF};
	for (int bit = LOG-1; bit >= 0; bit--){
		if (tol(bit)&k){
			ans[1]=max(ans[1],pa[node][bit]);
			ans[2]=min(ans[2],mi[node][bit]);
			ans[0]=st[ans[0]][bit];
		}
	}
	return ans;
}
int lca(int a, int b){
	if (dep[a]<dep[b]) swap(a,b);
	array<int,3> pr = kthpar(a,dep[a]-dep[b]);
	a=pr[0];
	int ans = pr[1];
	if (a==b) return ans;
	for (int bit = LOG-1; bit >= 0; bit--){
		if (st[a][bit]==st[b][bit]) continue;
		ans=max(ans,pa[a][bit]);
		ans=max(ans,pa[b][bit]);
		a=st[a][bit];
		b=st[b][bit];
	}
	ans=max(pa[a][0],ans);
	ans=max(pa[b][0],ans);
	return ans;
}
int centik(int a, int b){
	if (dep[a]<dep[b]) swap(a,b);
	if (dep[a]-dep[b]==1) return min(val[a],val[b]);
	array<int,3> pr = kthpar(a,dep[a]-dep[b]);
	if (pr[0]==b){
		int ans = min(val[a],val[b]);
		ans=min(ans,kthpar(st[a][0],dep[a]-dep[b]-1)[2]);
		return ans;
	}
	int ans = min(val[a],val[b]);
	a=st[a][0];
	b=st[b][0];
	pr = kthpar(a,dep[a]-dep[b]);
	a=pr[0];
	ans=min(ans,pr[2]);
	if (a==b){
		return min(ans,min(val[a],c3[a])); 
	}
	for (int bit = LOG-1; bit >= 0; bit--){
		if (st[a][bit]==st[b][bit]) continue;
		ans=min(ans,mi[a][bit]);
		ans=min(ans,mi[b][bit]);
		a=st[a][bit];
		b=st[b][bit];
	}
	a=st[a][0];
	return min(ans,min(val[a],c3[a]));
}
int32_t getMinimumFuelCapacity(int32_t X, int32_t Y){
	int ans = max(lca(X,Y),centik(X,Y));
	if (ans==INF) ans = -1;
	return ans;
}

#ifdef tolbi
int32_t main() {
	int32_t N, M;
	assert(2 == scanf("%d %d", &N, &M));

	vector<int32_t> U(M), V(M), W(M);
	for (int32_t i = 0; i < M; ++i) {
		assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
	}

	int32_t Q;
	assert(1 == scanf("%d", &Q));

	vector<int32_t> X(Q), Y(Q);
	for (int32_t i = 0; i < Q; ++i) {
		assert(2 == scanf("%d %d", &X[i], &Y[i]));
	}

	init(N, M, U, V, W);

	vector<int32_t> minimum_fuel_capacities(Q);
	for (int32_t i = 0; i < Q; ++i) {
		minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
		cout<<minimum_fuel_capacities[i]<<endl;
	}

	return 0;
}
#endif

Compilation message

swap.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
swap.cpp: In instantiation of 'init(int32_t, int32_t, std::vector<int>, std::vector<int>, std::vector<int>)::<lambda(long long int, long long int, auto:23)> [with auto:23 = init(int32_t, int32_t, std::vector<int>, std::vector<int>, std::vector<int>)::<lambda(long long int, long long int, auto:23)>]':
swap.cpp:117:14:   required from here
swap.cpp:100:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   for (int i = 0; i < arr[node].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 194 ms 60460 KB Output is correct
10 Correct 235 ms 75520 KB Output is correct
11 Correct 225 ms 73728 KB Output is correct
12 Correct 257 ms 78288 KB Output is correct
13 Correct 256 ms 79940 KB Output is correct
14 Correct 242 ms 59720 KB Output is correct
15 Correct 901 ms 77292 KB Output is correct
16 Correct 816 ms 73360 KB Output is correct
17 Correct 747 ms 82092 KB Output is correct
18 Correct 836 ms 79892 KB Output is correct
19 Incorrect 163 ms 13796 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 278 ms 68472 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Incorrect 1 ms 852 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 194 ms 60460 KB Output is correct
11 Correct 235 ms 75520 KB Output is correct
12 Correct 225 ms 73728 KB Output is correct
13 Correct 257 ms 78288 KB Output is correct
14 Correct 256 ms 79940 KB Output is correct
15 Correct 1 ms 852 KB Output is correct
16 Incorrect 1 ms 852 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 194 ms 60460 KB Output is correct
10 Correct 235 ms 75520 KB Output is correct
11 Correct 225 ms 73728 KB Output is correct
12 Correct 257 ms 78288 KB Output is correct
13 Correct 256 ms 79940 KB Output is correct
14 Correct 242 ms 59720 KB Output is correct
15 Correct 901 ms 77292 KB Output is correct
16 Correct 816 ms 73360 KB Output is correct
17 Correct 747 ms 82092 KB Output is correct
18 Correct 836 ms 79892 KB Output is correct
19 Incorrect 278 ms 68472 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 194 ms 60460 KB Output is correct
11 Correct 235 ms 75520 KB Output is correct
12 Correct 225 ms 73728 KB Output is correct
13 Correct 257 ms 78288 KB Output is correct
14 Correct 256 ms 79940 KB Output is correct
15 Correct 242 ms 59720 KB Output is correct
16 Correct 901 ms 77292 KB Output is correct
17 Correct 816 ms 73360 KB Output is correct
18 Correct 747 ms 82092 KB Output is correct
19 Correct 836 ms 79892 KB Output is correct
20 Incorrect 278 ms 68472 KB Output isn't correct
21 Halted 0 ms 0 KB -