oj.uz

Submission #744384

# Submission time Handle Problem Language Result Execution time Memory
744384 2023-05-18T14:04:13 Z tolbi Swapping Cities (APIO20_swap) C++17
44 / 100
 2000 ms 84048 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"
struct DSU{
	vector<int> par;
	DSU(int n){
		par.resize(n);
		iota(par.begin(), par.end(), 0);
	}
	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;
	}
	bool same(int a, int b){
		a=find(a);
		b=find(b);
		return (a==b);
	}
};
vector<int> c2;
vector<int> c3;
vector<int> up;
vector<int> par;
vector<int> dep;
vector<vector<pair<int,int>>> arr;
vector<int> c2dp;
vector<int> val;
vector<vector<int>> st;
vector<vector<int>> ma;
vector<vector<int>> mi;
int LOG;
int getc2(int node){
	if (c2dp[node]!=-1) return c2dp[node];
	int ans = c2[node];
	for (int i = 0; i < arr[node].size(); i++){
		if (arr[node][i].first==par[node]) continue;
		ans=min(ans,max(getc2(arr[node][i].first),arr[node][i].second));
	}
	return c2dp[node]=ans;
}
void init(int32_t N, int32_t M, vector<int32_t> U, vector<int32_t> V, vector<int32_t> W) {
	LOG = log2(N)+3;
	st.resize(N,vector<int>(LOG,-1));
	ma.resize(N,vector<int>(LOG,0));
	mi.resize(N,vector<int>(LOG,INF));
	arr.resize(N);
	c2.resize(N,INF);
	c3.resize(N,INF);
	up.resize(N,INF);
	c2dp.resize(N,-1);
	par.resize(N,-1);
	dep.resize(N,0);
	val.resize(N,INF);
	DSU dsu(N);
	vector<pair<int,pair<int,int>>> ed(M);
	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 (dsu.same(u,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});
		dsu.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 indi = 0;
		for (int i = 0; i < arr[node].size(); i++){
			if (arr[node][i].first==lnode) continue;
			par[arr[node][i].first]=node;
			dep[arr[node][i].first]=dep[node]+1;
			up[arr[node][i].first]=arr[node][i].second;
			indi++;
			if (indi==2){
				c2[node]=arr[node][i].second;
			}
			else if (indi==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]));
		}
	};
	dfs(0,-1,dfs);
	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(val[node],arr[node][i].second));
			dfs2(arr[node][i].first,node,dfs2);
		}
	};
	dfs2(0,-1,dfs2);
	for (int i = 1; i < N; i++){
		st[i][0]=par[i];
		ma[i][0]=up[i];
		mi[i][0]=getc2(i);
	}
	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]);
		}
	}
}
bool isancestor(int X, int Y){
	int k = dep[X]-dep[Y];
	for (int bit = LOG-1; bit >= 0; bit--){
		if (tol(bit)&k){
			X=st[X][bit];
		}
	}
	return (X==Y);
}
int32_t getMinimumFuelCapacity(int32_t X, int32_t Y){
	if (dep[X]<dep[Y]) swap(X,Y);
	if (isancestor(X,Y)){
		int ans = 0;
		int ans2 = val[X];
		while (X!=Y){
			ans2=min(ans2,getc2(X));
			ans=max(ans,up[X]);
			if (par[X]==Y) break;
			X=par[X];
		}
		int crr = 0;
		while (Y!=-1){
			if (crr>=ans2) break;
			ans2=min(ans2,max(crr,max(c2[Y],up[Y])));
			ans2=min(ans2,max(crr,c3[Y]));
			for (int i = 0; i < arr[Y].size(); i++){
				if (arr[Y][i].first==X) continue;
				if (arr[Y][i].first==par[Y]) continue;
				ans2=min(ans2,max(crr,max(getc2(arr[Y][i].first),arr[Y][i].second)));
			}
			X=Y;
			crr=max(crr,up[Y]);
			Y=par[Y];
		}
		ans=max(ans,ans2);
		if (ans==INF) ans = -1;
		return ans;//O(N)
	}
	else {
		int ans = 0;
		int ans2 = INF;
		if (dep[X]>dep[Y]){
			int k = dep[X]-dep[Y];
			for (int bit = LOG-1; bit >= 0; bit--){
				if (tol(bit)&k){
					ans2=min(ans2,mi[X][bit]);
					ans=max(ans,ma[X][bit]);
					X=st[X][bit];
				}
			}
		}
		for (int bit = LOG-1; bit >= 0; bit--){
			if (st[X][bit]==st[Y][bit]) continue;
			ans2=min(ans2,mi[X][bit]);
			ans2=min(ans2,mi[Y][bit]);
			ans=max(ans,ma[X][bit]);
			ans=max(ans,ma[Y][bit]);
			X=st[X][bit];
			Y=st[Y][bit];
		}
		ans2=min(ans2,mi[X][0]);
		ans2=min(ans2,mi[Y][0]);
		ans=max(ans,ma[X][0]);
		ans=max(ans,ma[Y][0]);
		X=st[X][0];
		Y=st[Y][0];
		ans2=min(ans2,min(up[X],c3[X]));
		ans2=min(ans2,val[X]);
		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 function 'long long int getc2(long long int)':
swap.cpp:78:20: 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]
   78 |  for (int i = 0; i < arr[node].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~~~
swap.cpp: In lambda function:
swap.cpp:123: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]
  123 |   for (int i = 0; i < arr[node].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~
swap.cpp: In lambda function:
swap.cpp:141: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]
  141 |   for (int i = 0; i < arr[node].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~
swap.cpp: In function 'int32_t getMinimumFuelCapacity(int32_t, int32_t)':
swap.cpp:187:22: 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]
  187 |    for (int i = 0; i < arr[Y].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: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:139:14:   required from here
swap.cpp:123: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]
  123 |   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:147:16:   required from here
swap.cpp:141: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]
  141 |   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 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 836 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 196 ms 61668 KB Output is correct
10 Correct 263 ms 76300 KB Output is correct
11 Correct 264 ms 74620 KB Output is correct
12 Correct 272 ms 79316 KB Output is correct
13 Correct 253 ms 80076 KB Output is correct
14 Execution timed out 2091 ms 61248 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 260 ms 72004 KB Output is correct
4 Correct 270 ms 75960 KB Output is correct
5 Correct 286 ms 73016 KB Output is correct
6 Correct 277 ms 75528 KB Output is correct
7 Correct 271 ms 74200 KB Output is correct
8 Correct 270 ms 71264 KB Output is correct
9 Correct 282 ms 73920 KB Output is correct
10 Correct 263 ms 70600 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 836 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 1 ms 300 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 1 ms 724 KB Output is correct
14 Correct 1 ms 724 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 832 KB Output is correct
19 Correct 2 ms 724 KB Output is correct
20 Correct 2 ms 852 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 724 KB Output is correct
24 Correct 2 ms 980 KB Output is correct
25 Correct 2 ms 864 KB Output is correct
26 Correct 2 ms 960 KB Output is correct
27 Correct 1 ms 832 KB Output is correct
28 Correct 2 ms 964 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 440 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 2 ms 836 KB Output is correct
9 Correct 2 ms 844 KB Output is correct
10 Correct 196 ms 61668 KB Output is correct
11 Correct 263 ms 76300 KB Output is correct
12 Correct 264 ms 74620 KB Output is correct
13 Correct 272 ms 79316 KB Output is correct
14 Correct 253 ms 80076 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 1 ms 724 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 2 ms 852 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 2 ms 852 KB Output is correct
23 Correct 2 ms 832 KB Output is correct
24 Correct 2 ms 724 KB Output is correct
25 Correct 2 ms 852 KB Output is correct
26 Correct 2 ms 852 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 724 KB Output is correct
29 Correct 2 ms 980 KB Output is correct
30 Correct 2 ms 864 KB Output is correct
31 Correct 2 ms 960 KB Output is correct
32 Correct 1 ms 832 KB Output is correct
33 Correct 2 ms 964 KB Output is correct
34 Correct 18 ms 9812 KB Output is correct
35 Correct 274 ms 78644 KB Output is correct
36 Correct 253 ms 76648 KB Output is correct
37 Correct 248 ms 75324 KB Output is correct
38 Correct 234 ms 74000 KB Output is correct
39 Correct 214 ms 73292 KB Output is correct
40 Correct 171 ms 67328 KB Output is correct
41 Correct 277 ms 77564 KB Output is correct
42 Correct 274 ms 78152 KB Output is correct
43 Correct 232 ms 78572 KB Output is correct
44 Correct 228 ms 75340 KB Output is correct
45 Correct 175 ms 63448 KB Output is correct
46 Correct 269 ms 75956 KB Output is correct
47 Correct 227 ms 74388 KB Output is correct
48 Correct 187 ms 73528 KB Output is correct
49 Correct 63 ms 11056 KB Output is correct
50 Correct 52 ms 12616 KB Output is correct
51 Correct 152 ms 52220 KB Output is correct
52 Correct 266 ms 80424 KB Output is correct
53 Correct 224 ms 81016 KB Output is correct
54 Correct 298 ms 84048 KB Output is correct
55 Correct 223 ms 79436 KB Output is correct
56 Correct 255 ms 79732 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 836 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 196 ms 61668 KB Output is correct
10 Correct 263 ms 76300 KB Output is correct
11 Correct 264 ms 74620 KB Output is correct
12 Correct 272 ms 79316 KB Output is correct
13 Correct 253 ms 80076 KB Output is correct
14 Execution timed out 2091 ms 61248 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 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 440 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 2 ms 836 KB Output is correct
9 Correct 2 ms 844 KB Output is correct
10 Correct 196 ms 61668 KB Output is correct
11 Correct 263 ms 76300 KB Output is correct
12 Correct 264 ms 74620 KB Output is correct
13 Correct 272 ms 79316 KB Output is correct
14 Correct 253 ms 80076 KB Output is correct
15 Execution timed out 2091 ms 61248 KB Time limit exceeded
16 Halted 0 ms 0 KB -