oj.uz

Submission #743387

# Submission time Handle Problem Language Result Execution time Memory
743387 2023-05-17T11:03:41 Z tolbi Swapping Cities (APIO20_swap) C++17
6 / 100
 496 ms 59604 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<pair<int,int>>> st;
int LOG;
int find(int node){
	if (par[node]==node) return node;
	return par[node]=find(par[node]);
}
vector<int> val;
void init(int32_t N, int32_t M, vector<int32_t> U, vector<int32_t> V, vector<int32_t> W) {
	vector<pair<int,pair<int,int>>> edges(M);
	LOG=log2(N)+3;
	par.resize(N);
	dep.resize(N);
	iota(par.begin(), par.end(), 0);
	vector<vector<pair<int,int>>> arr(N);
	val.resize(N,INF);
	for (int i = 0; i < M; i++){
		edges[i]={W[i],{U[i],V[i]}};
	}
	sortarr(edges);
	for (int i = 0; i < M; i++){
		auto [u,v] = edges[i].second;
		int w = edges[i].first;
		if (find(u)==find(v)){
			if (val[u]==INF) val[u]=w;
			if (val[v]==INF) 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;
	}
	st.resize(N,vector<pair<int,int>>(LOG,{-1,-1}));
	auto dfs = [&](int node, int lnode, auto dfs)->void{
		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;
			dfs(arr[node][i].first,node,dfs);
			st[arr[node][i].first][0]={node,arr[node][i].second};
			val[node]=min(val[node],max(val[arr[node][i].first],arr[node][i].second));
		}
	};
	auto dfs2 = [&](int node, int lnode, auto dfs2)->void{
		if (node){
			val[node]=min(val[node],max(val[lnode],st[node][0].second));
		}
		for (int i = 0; i < arr[node].size(); i++){
			if (arr[node][i].first==lnode) continue;
			dfs2(arr[node][i].first,node,dfs2);
		}
	};
	dfs(0,-1,dfs);
	dfs2(0,-1,dfs2);
	for (int bit = 1; bit < LOG; bit++){
		for (int i = 0; i < N; i++){
			if (st[i][bit-1].first==-1) continue;
			st[i][bit].first=st[st[i][bit-1].first][bit-1].first;
			st[i][bit].second=max(st[i][bit-1].second,st[st[i][bit-1].first][bit-1].second);
		}
	}
}
pair<int,int> kthpar(int node, int k){
	int rval = 0ll;
	for (int bit = LOG-1; bit >= 0; bit--){
		if (tol(bit)&k){
			rval=max(rval,st[node][bit].second);
			node=st[node][bit].first;
		}
	}
	return {node,rval};
}
pair<int,int> lca(int a, int b){
	if (dep[a]<dep[b]) swap(a,b);
	pair<int,int> pr = kthpar(a,dep[a]-dep[b]);
	a=pr.first;
	int ans = pr.second;
	if (a==b) return {a,ans};
	for (int bit = LOG-1; bit >= 0; bit--){
		if (st[a][bit].first==st[b][bit].first) continue;
		ans=max(ans,st[a][bit].second);
		ans=max(ans,st[b][bit].second);
		a=st[a][bit].first;
		b=st[b][bit].first;
	}
	ans=max(ans,st[a][0].second);
	ans=max(ans,st[b][0].second);
	return {st[a][0].first,ans};
}
int32_t getMinimumFuelCapacity(int32_t X, int32_t Y){
	pair<int,int> ans = lca(X,Y);
	if (max(ans.second,val[ans.first])==INF) return -1;
	return max(ans.second,val[ans.first]);
}

#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]);
	}

	for (int32_t i = 0; i < Q; ++i) {
		printf("%d\n", minimum_fuel_capacities[i]);
	}

	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:99:14:   required from here
swap.cpp:83: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]
   83 |   for (int i = 0; i < arr[node].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~
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:24)> [with auto:24 = init(int32_t, int32_t, std::vector<int>, std::vector<int>, std::vector<int>)::<lambda(long long int, long long int, auto:24)>]':
swap.cpp:100:16:   required from here
swap.cpp:94: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]
   94 |   for (int i = 0; i < arr[node].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 1 ms 568 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 142 ms 42388 KB Output is correct
10 Correct 179 ms 52508 KB Output is correct
11 Correct 186 ms 51420 KB Output is correct
12 Correct 183 ms 54604 KB Output is correct
13 Correct 161 ms 55244 KB Output is correct
14 Correct 157 ms 42136 KB Output is correct
15 Correct 467 ms 56592 KB Output is correct
16 Correct 458 ms 54084 KB Output is correct
17 Correct 364 ms 59604 KB Output is correct
18 Correct 369 ms 58060 KB Output is correct
19 Correct 85 ms 12628 KB Output is correct
20 Correct 445 ms 56200 KB Output is correct
21 Correct 494 ms 53708 KB Output is correct
22 Correct 496 ms 58184 KB Output is correct
23 Correct 425 ms 57784 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Incorrect 216 ms 50748 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 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 1 ms 568 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Incorrect 1 ms 576 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 440 KB Output is correct
6 Correct 1 ms 568 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 142 ms 42388 KB Output is correct
11 Correct 179 ms 52508 KB Output is correct
12 Correct 186 ms 51420 KB Output is correct
13 Correct 183 ms 54604 KB Output is correct
14 Correct 161 ms 55244 KB Output is correct
15 Incorrect 1 ms 576 KB Output isn't correct
16 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 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 1 ms 568 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 142 ms 42388 KB Output is correct
10 Correct 179 ms 52508 KB Output is correct
11 Correct 186 ms 51420 KB Output is correct
12 Correct 183 ms 54604 KB Output is correct
13 Correct 161 ms 55244 KB Output is correct
14 Correct 157 ms 42136 KB Output is correct
15 Correct 467 ms 56592 KB Output is correct
16 Correct 458 ms 54084 KB Output is correct
17 Correct 364 ms 59604 KB Output is correct
18 Correct 369 ms 58060 KB Output is correct
19 Incorrect 216 ms 50748 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 440 KB Output is correct
6 Correct 1 ms 568 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 142 ms 42388 KB Output is correct
11 Correct 179 ms 52508 KB Output is correct
12 Correct 186 ms 51420 KB Output is correct
13 Correct 183 ms 54604 KB Output is correct
14 Correct 161 ms 55244 KB Output is correct
15 Correct 157 ms 42136 KB Output is correct
16 Correct 467 ms 56592 KB Output is correct
17 Correct 458 ms 54084 KB Output is correct
18 Correct 364 ms 59604 KB Output is correct
19 Correct 369 ms 58060 KB Output is correct
20 Incorrect 216 ms 50748 KB Output isn't correct
21 Halted 0 ms 0 KB -