oj.uz

Submission #743909

# Submission time Handle Problem Language Result Execution time Memory
743909 2023-05-18T06:01:02 Z tolbi Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 81456 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());
vector<vector<int>> st;			//bitmedi
vector<vector<int>> ma;			//bitmedi
vector<vector<int>> mi;			//bitmedi
vector<int> dep;				//bitti
vector<int> val;				//bitti
vector<int> c2;					//bitti
vector<int> c3;					//bitti
vector<int> par;				//bitti
int LOG;
int find(int node){
	if (par[node]==node) return node;
	return par[node]=find(par[node]);
}
void merge(int a, int b){
	a=find(a);
	b=find(b);
	if (ayahya()%2) swap(a,b);
	par[a]=b;
}
#include "swap.h"
void init(int32_t N, int32_t M, vector<int32_t> U, vector<int32_t> V, vector<int32_t> W) {
	LOG = log2(N)+3;
	vector<pair<int,pair<int,int>>> ed(M);
	par.resize(N);
	dep.resize(N);
	val.resize(N,INF);
	c2.resize(N,INF);
	c3.resize(N,INF);
	mi.resize(N,vector<int>(LOG,INF));
	ma.resize(N,vector<int>(LOG,0));
	st.resize(N,vector<int>(LOG,-1));
	vector<vector<pair<int,int>>> arr(N);
	iota(par.begin(), par.end(), 0);
	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});
		merge(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 it = 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;
			it++;
			if (it==2){
				c2[node]=arr[node][i].second;
			}
			else if (it==3){
				c3[node]=arr[node][i].second;
			}
			dfs(arr[node][i].first,node,dfs);
			val[node]=min(val[node],max(arr[node][i].second,val[arr[node][i].first]));
			st[arr[node][i].first][0]=node;
			ma[arr[node][i].first][0]=arr[node][i].second;
			mi[node][0]=c2[node];
		}
	};
	auto dfs2 = [&](int node, int lnode, auto dfs2)->void{
		for (int i = 0; i < arr[node].size(); i++){
			if (arr[node][i].first==lnode) continue;
			val[arr[node][i].first]=min(val[arr[node][i].first],max(arr[node][i].second,val[node]));
			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]==-1) continue;
			st[i][bit]=st[st[i][bit-1]][bit-1];
			ma[i][bit]=max(ma[i][bit-1],ma[st[i][bit-1]][bit-1]);
			mi[i][bit]=min(mi[i][bit-1],mi[st[i][bit-1]][bit-1]);
		}
	}
}
int32_t getMinimumFuelCapacity(int32_t X, int32_t Y){
	pair<pair<int,bool>,pair<int,bool>> pr={{X,true},{Y,true}};
	int ans = 0;
	int ans2 = INF;
	while (pr.first.first!=pr.second.first){
		if (dep[pr.first.first]<dep[pr.second.first]){
			swap(pr.first,pr.second);
		}
		if (!pr.first.second){
			ans2=min(ans2,c2[pr.first.first]);
		}
		ans2=min(ans2,val[pr.first.first]);
		ans=max(ans,ma[pr.first.first][0]);
		pr.first.second=false;
		pr.first.first=st[pr.first.first][0];
	}
	ans2=min(ans2,val[pr.first.first]);
	if (pr.first.second==false && pr.second.second==false){
		ans2=min(ans2,c3[pr.first.first]);
		if (pr.first.first!=0) ans2=min(ans2,ma[pr.first.first][0]);
	}
	ans=max(ans,ans2);
	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:122:14:   required from here
swap.cpp:99: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]
   99 |   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:123:16:   required from here
swap.cpp:116: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]
  116 |   for (int i = 0; i < arr[node].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 824 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 828 KB Output is correct
8 Correct 2 ms 952 KB Output is correct
9 Correct 247 ms 61456 KB Output is correct
10 Correct 311 ms 76868 KB Output is correct
11 Correct 317 ms 74876 KB Output is correct
12 Correct 347 ms 79716 KB Output is correct
13 Correct 371 ms 81456 KB Output is correct
14 Execution timed out 2058 ms 60900 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 824 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 828 KB Output is correct
8 Correct 2 ms 952 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 2 ms 696 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Incorrect 2 ms 852 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 824 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 2 ms 828 KB Output is correct
9 Correct 2 ms 952 KB Output is correct
10 Correct 247 ms 61456 KB Output is correct
11 Correct 311 ms 76868 KB Output is correct
12 Correct 317 ms 74876 KB Output is correct
13 Correct 347 ms 79716 KB Output is correct
14 Correct 371 ms 81456 KB Output is correct
15 Correct 2 ms 852 KB Output is correct
16 Correct 2 ms 852 KB Output is correct
17 Correct 2 ms 852 KB Output is correct
18 Correct 2 ms 696 KB Output is correct
19 Correct 2 ms 724 KB Output is correct
20 Incorrect 2 ms 852 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 824 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 828 KB Output is correct
8 Correct 2 ms 952 KB Output is correct
9 Correct 247 ms 61456 KB Output is correct
10 Correct 311 ms 76868 KB Output is correct
11 Correct 317 ms 74876 KB Output is correct
12 Correct 347 ms 79716 KB Output is correct
13 Correct 371 ms 81456 KB Output is correct
14 Execution timed out 2058 ms 60900 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 824 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 2 ms 828 KB Output is correct
9 Correct 2 ms 952 KB Output is correct
10 Correct 247 ms 61456 KB Output is correct
11 Correct 311 ms 76868 KB Output is correct
12 Correct 317 ms 74876 KB Output is correct
13 Correct 347 ms 79716 KB Output is correct
14 Correct 371 ms 81456 KB Output is correct
15 Execution timed out 2058 ms 60900 KB Time limit exceeded
16 Halted 0 ms 0 KB -