oj.uz

Submission #743415

# Submission time Handle Problem Language Result Execution time Memory
743415 2023-05-17T11:29:51 Z tolbi Swapping Cities (APIO20_swap) C++17
0 / 100
 527 ms 93792 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;
vector<vector<pair<int,int>>> st2;
vector<int> vv;
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);
	vv.resize(N,INF);
	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}));
	st2.resize(N,vector<pair<int,int>>(LOG,{-1,INF}));
	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{
		if (lnode==-1) dep[node]=0;
		else dep[node]=dep[lnode]+1;
		int indi = 0;
		for (int i = 0; i < arr[node].size(); i++){
			if (arr[node][i].first==lnode) continue;
			indi++;
			if (indi==2){
				st2[node][0].second=arr[node][i].second;
			}
			if (indi==3){
				vv[node]=arr[node][i].second;
			}
			dfs(arr[node][i].first,node,dfs);
			st[arr[node][i].first][0]={node,arr[node][i].second};
			st2[arr[node][i].first][0].first=node;
			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);
		}
	}
	for (int bit = 1; bit < LOG; bit++){
		for (int i = 0; i < N; i++){
			if (st2[i][bit-1].first==-1) continue;
			st2[i][bit].first=st2[st2[i][bit-1].first][bit-1].first;
			st2[i][bit].second=min(st2[i][bit-1].second,st2[st2[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};
}
pair<int,int> kthpar2(int node, int k){
	int rval = INF;
	for (int bit = LOG-1; bit >= 0; bit--){
		if (tol(bit)&k){
			rval=min(rval,st2[node][bit].second);
			node=st2[node][bit].first;
		}
	}
	return {node,rval};
}
int lca2(int a, int b){
	int ans = INF;
	if (dep[a]!=dep[b]){
		if (dep[a]<dep[b]) swap(a,b);
		a=st[a][0].first;
		pair<int,int> pr = kthpar2(a,dep[a]-dep[b]);
		a=pr.first;
		ans = pr.second;
		if (a==b) return ans;
		b=st[b][0].first;
	}
	else {
		a=st[a][0].first;
		b=st[b][0].first;
	}
	for (int bit = LOG-1; bit >= 0; bit--){
		if (st2[a][bit].first==st2[b][bit].first) continue;
		ans=min(ans,st2[a][bit].second);
		ans=min(ans,st2[b][bit].second);
		a=st2[a][bit].first;
		b=st2[b][bit].first;
	}
	ans=min(ans,st[a][0].second);
	ans=min(ans,st[b][0].second);
	return 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;
	int kk = val[ans.first];
	if (ans.first) kk=min(kk,st[ans.first][0].second);
	kk=min(kk,lca2(X,Y));
	kk=min(kk,vv[ans.first]);
	return max(ans.second,kk);
}

#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:118:14:   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++){
      |                   ~~^~~~~~~~~~~~~~~~~~
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:119:16:   required from here
swap.cpp:113: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]
  113 |   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 1 ms 256 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 2 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 2 ms 980 KB Output is correct
9 Correct 190 ms 69796 KB Output is correct
10 Correct 247 ms 86768 KB Output is correct
11 Correct 239 ms 84832 KB Output is correct
12 Correct 249 ms 90144 KB Output is correct
13 Correct 221 ms 91856 KB Output is correct
14 Correct 217 ms 68864 KB Output is correct
15 Correct 480 ms 88592 KB Output is correct
16 Correct 527 ms 84356 KB Output is correct
17 Correct 514 ms 93792 KB Output is correct
18 Correct 449 ms 91596 KB Output is correct
19 Runtime error 62 ms 29032 KB Execution killed with signal 11
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 1 ms 256 KB Output is correct
3 Incorrect 252 ms 79592 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 256 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 2 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 2 ms 980 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 1 ms 852 KB Output isn't correct
11 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 1 ms 256 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 2 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 190 ms 69796 KB Output is correct
11 Correct 247 ms 86768 KB Output is correct
12 Correct 239 ms 84832 KB Output is correct
13 Correct 249 ms 90144 KB Output is correct
14 Correct 221 ms 91856 KB Output is correct
15 Incorrect 1 ms 852 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 256 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 2 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 2 ms 980 KB Output is correct
9 Correct 190 ms 69796 KB Output is correct
10 Correct 247 ms 86768 KB Output is correct
11 Correct 239 ms 84832 KB Output is correct
12 Correct 249 ms 90144 KB Output is correct
13 Correct 221 ms 91856 KB Output is correct
14 Correct 217 ms 68864 KB Output is correct
15 Correct 480 ms 88592 KB Output is correct
16 Correct 527 ms 84356 KB Output is correct
17 Correct 514 ms 93792 KB Output is correct
18 Correct 449 ms 91596 KB Output is correct
19 Incorrect 252 ms 79592 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 1 ms 256 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 2 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 190 ms 69796 KB Output is correct
11 Correct 247 ms 86768 KB Output is correct
12 Correct 239 ms 84832 KB Output is correct
13 Correct 249 ms 90144 KB Output is correct
14 Correct 221 ms 91856 KB Output is correct
15 Correct 217 ms 68864 KB Output is correct
16 Correct 480 ms 88592 KB Output is correct
17 Correct 527 ms 84356 KB Output is correct
18 Correct 514 ms 93792 KB Output is correct
19 Correct 449 ms 91596 KB Output is correct
20 Incorrect 252 ms 79592 KB Output isn't correct
21 Halted 0 ms 0 KB -