oj.uz

Submission #744260

# Submission time Handle Problem Language Result Execution time Memory
744260 2023-05-18T10:04:44 Z tolbi Swapping Cities (APIO20_swap) C++17
7 / 100
 2000 ms 524288 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> c2;
vector<int> c3;
vector<int> up;
vector<int> par;
vector<int> dep;
vector<vector<pair<int,int>>> arr;
vector<int> c2dp;
void init(int32_t N, int32_t M, vector<int32_t> U, vector<int32_t> V, vector<int32_t> W) {
	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);
	for (int i = 0; i < M; i++){
		arr[U[i]].push_back({V[i],W[i]});
		arr[V[i]].push_back({U[i],W[i]});
	}
	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);
		}
	};
	dfs(0,-1,dfs);
}
bool isancestor(int X, int Y){
	while (X!=-1){
		if (X==Y) return true;
		X=par[X];
	}
	return false;
}
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;
}
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 = INF;
		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(c2[Y],up[Y]));
			ans2=min(ans2,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(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;
	}
	else {
		int ans = 0;
		int ans2 = INF;
		while (X!=Y){
			if (dep[X]<dep[Y]) swap(X,Y);
			ans2=min(ans2,getc2(X));
			ans=max(ans,up[X]);
			X=par[X];
		}
		ans2=min(ans2,min(up[X],c3[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 lambda function:
swap.cpp:67: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]
   67 |   for (int i = 0; i < arr[node].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~
swap.cpp: In function 'long long int getc2(long long int)':
swap.cpp:94: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]
   94 |  for (int i = 0; i < arr[node].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~~~
swap.cpp: In function 'int32_t getMinimumFuelCapacity(int32_t, int32_t)':
swap.cpp:116: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]
  116 |    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:82:14:   required from here
swap.cpp:67: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]
   67 |   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 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 448 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 62 ms 15548 KB Output is correct
10 Correct 100 ms 19596 KB Output is correct
11 Correct 94 ms 18972 KB Output is correct
12 Correct 96 ms 20296 KB Output is correct
13 Correct 88 ms 21212 KB Output is correct
14 Execution timed out 2074 ms 15412 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 121 ms 20444 KB Output is correct
4 Correct 116 ms 21000 KB Output is correct
5 Correct 131 ms 21028 KB Output is correct
6 Correct 117 ms 20892 KB Output is correct
7 Correct 120 ms 21112 KB Output is correct
8 Correct 119 ms 20332 KB Output is correct
9 Correct 120 ms 20872 KB Output is correct
10 Correct 114 ms 20300 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 448 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Runtime error 366 ms 524288 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 366 ms 524288 KB Execution killed with signal 9
2 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 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 448 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 62 ms 15548 KB Output is correct
10 Correct 100 ms 19596 KB Output is correct
11 Correct 94 ms 18972 KB Output is correct
12 Correct 96 ms 20296 KB Output is correct
13 Correct 88 ms 21212 KB Output is correct
14 Execution timed out 2074 ms 15412 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 366 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -