oj.uz

Submission #922642

# Submission time Handle Problem Language Result Execution time Memory
922642 2024-02-05T21:14:34 Z tolbi Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 96 ms 10484 KB 
#pragma optimize("Bismillahirrahmanirrahim")
#pragma optimize("HIZLAN ASLANIM BENIM")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//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> 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());
namespace Graph{
	vector<int> BFS(vector<vector<pair<int,int>>> &arr, int src){
		int n = arr.size();
		priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
		vector<int> dp(n,-1);
		pq.push({0,src});
		while (pq.size()){
			int node = pq.top().second;
			int w = pq.top().first;
			pq.pop();
			if (dp[node]!=-1) continue;
			dp[node]=w;
			for (int i = 0; i < arr[node].size(); i++){
				pq.push({w+arr[node][i].second,arr[node][i].first});
			}
		}
		return dp;
	}
	int BFS(vector<vector<array<int,3>>> &arr, int src, int target, int yasak){
		int n = arr.size();
		priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
		vector<int> dp(n,-1);
		pq.push({0,src});
		while (pq.size()){
			int node = pq.top().second;
			int w = pq.top().first;
			pq.pop();
			if (dp[node]!=-1) continue;
			if (node==target) return w;
			dp[node]=w;
			for (int i = 0; i < arr[node].size(); i++){
				if (arr[node][i][2]==yasak) continue;
				pq.push({w+arr[node][i][1],arr[node][i][0]});
			}
		}
		return -1;
	}
	vector<pair<int,int>> BFS(vector<vector<array<int,3>>> &arr, int src){
		int n = arr.size();
		priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> pq;
		pq.push({0,src,-1});
		vector<pair<int,int>> dp(n,{-1,-1});
		while (pq.size()){
			int w = pq.top()[0];
			int node = pq.top()[1];
			int ind = pq.top()[2];
			pq.pop();
			if (dp[node].first!=-1) continue;
			dp[node]={node,ind};
			for (int i = 0; i < arr[node].size(); i++){
				pq.push({w+arr[node][i][1],arr[node][i][0],arr[node][i][2]});
			}
		}
		return dp;
	}
};
int32_t main(){
	ios;
	int t=1;
	int tno = 0;
	if (!t) cin>>t;
	while (t-(tno++)){
		deci(n);deci(m);
		vector<array<int,2>> edges;
		vector<vector<pair<int,int>>> duz(n);
		vector<vector<pair<int,int>>> ters(n);
		vector<vector<array<int,3>>> hayd(n);
		vector<array<int,4>> ed(m);
		cinarr(ed);
		for (int i = 0; i < m; ++i)
		{
			ed[i][0]--,ed[i][1]--;
			duz[ed[i][0]].push_back({ed[i][1],ed[i][2]});
			ters[ed[i][1]].push_back({ed[i][0],ed[i][2]});
			hayd[ed[i][0]].push_back({ed[i][1],ed[i][2],i});
		}
		vector<int> 
		dp=Graph::BFS(duz,0),
		dp1=Graph::BFS(ters,0),
		dp2=Graph::BFS(duz,n-1),
		dp3=Graph::BFS(ters,n-1);
		vector<pair<int,int>> hh = Graph::BFS(hayd,0);
		vector<pair<int,int>> hh2 = Graph::BFS(hayd,n-1);
		vector<bool> kul(m,false);
		int nod = n-1;
		while (hh[nod].second!=-1){
			kul[hh[nod].second]=true;
			nod=ed[hh[nod].second][0];
		}
		nod=0;
		while (hh2[nod].second!=-1){
			kul[hh2[nod].second]=true;
			nod=ed[hh2[nod].second][0];
		}
		int ans = INF;
		if (dp[n-1]!=-1 && dp2[0]!=-1) ans=dp[n-1]+dp2[0];
		for (int i = 0; i < m; i++){
			int crr = INF;
			if (kul[i]){
				hayd[ed[i][1]].push_back({ed[i][0],ed[i][2],m});
				int a = Graph::BFS(hayd,0,n-1,i);
				int b = Graph::BFS(hayd,n-1,0,i);
				if (a==-1 || b==-1) continue;
				crr=a+b+ed[i][3];
				hayd[ed[i][1]].pop_back();
			}
			else {
				int git = INF;
				int don = INF;
				if (dp[n-1]!=-1) git=dp[n-1];
				if (dp2[0]!=-1) don=dp2[0];
				if (dp[ed[i][1]]!=-1 && dp3[ed[i][0]]!=-1){
					git=min(git,dp[ed[i][1]]+dp3[ed[i][0]]+ed[i][2]);
				}
				if (dp2[ed[i][1]]!=-1 && dp1[ed[i][0]]!=-1){
					don=min(don,dp2[ed[i][1]]+dp1[ed[i][0]]+ed[i][2]);
				}
				if (git!=INF && don!=INF) crr=git+don+ed[i][3];
			}
			ans=min(ans,crr);
		}
		if (ans==INF) ans=-1;
		cout<<ans<<endl;
	}
}

Compilation message

ho_t4.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
ho_t4.cpp:2: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    2 | #pragma optimize("HIZLAN ASLANIM BENIM")
      | 
ho_t4.cpp: In function 'std::vector<long long int> Graph::BFS(std::vector<std::vector<std::pair<long long int, long long int> > >&, long long int)':
ho_t4.cpp:49: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]
   49 |    for (int i = 0; i < arr[node].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~
ho_t4.cpp: In function 'long long int Graph::BFS(std::vector<std::vector<std::array<long long int, 3> > >&, long long int, long long int, long long int)':
ho_t4.cpp:67:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |    for (int i = 0; i < arr[node].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~
ho_t4.cpp: In function 'std::vector<std::pair<long long int, long long int> > Graph::BFS(std::vector<std::vector<std::array<long long int, 3> > >&, long long int)':
ho_t4.cpp:86:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |    for (int i = 0; i < arr[node].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 476 KB Output is correct
10 Correct 22 ms 604 KB Output is correct
11 Incorrect 32 ms 600 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 9140 KB Output is correct
2 Correct 65 ms 9860 KB Output is correct
3 Correct 61 ms 10216 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 556 KB Output is correct
9 Correct 30 ms 8680 KB Output is correct
10 Correct 28 ms 8352 KB Output is correct
11 Correct 96 ms 10092 KB Output is correct
12 Correct 71 ms 10408 KB Output is correct
13 Correct 76 ms 9972 KB Output is correct
14 Incorrect 80 ms 10484 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 476 KB Output is correct
10 Correct 22 ms 604 KB Output is correct
11 Incorrect 32 ms 600 KB Output isn't correct
12 Halted 0 ms 0 KB -