oj.uz

Submission #923348

# Submission time Handle Problem Language Result Execution time Memory
923348 2024-02-07T06:47:54 Z NotLinux Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 367 ms 6888 KB 
// put it before the include
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//author : FatihCihan
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
#define int long long
const int inf = 1e18 + 7;
void solve(){
	int n,m;
	cin >> n >> m;
	vector < vector < pair < int , int > > > graph(n+1) , igraph(n+1);
	array < int , 4 > edge[m];
	bool is_in_path[m];
	memset(is_in_path , 0 , sizeof(is_in_path));
	for(int i = 0;i<m;i++){
		cin >> edge[i][0] >> edge[i][1] >> edge[i][2] >> edge[i][3];
		graph[edge[i][0]].push_back({edge[i][1] , i});
		igraph[edge[i][1]].push_back({edge[i][0] , i});
	}
	auto eval = [&](int st , vector < vector < pair < int , int > > > G , int forbidden){
		vector < int > vis(n+1 , inf);
		vector < pair < int , int > >  pq(n+1 , {inf , inf});
		pq[st] = {0,-1};
		// cout << "forbidden : " << forbidden << endl;
		while(true){
			int tmp = -1;
			pair < int , int > val = {inf,inf};
			for(int i = 1;i<=n;i++){
				if(vis[i] == inf and val > pq[i]){
					tmp = i;
					val = pq[i];
				}
			}
			if(tmp == -1 or val.first == inf)break;
			// cout << "bfs : " << tmp << " " << val.first << " " << val.second << endl;
			vis[tmp] = val.first;
			if(val.second != -1 and forbidden == -1){
				is_in_path[val.second] = 1;
			}
			for(int i = 0;i<sz(G[tmp]);i++){
				if(G[tmp][i].second != forbidden){
					array < int , 4 > ed = edge[G[tmp][i].second];
					pq[ed[1]] = min(pq[ed[1]] , {val.first + ed[2] , G[tmp][i].second});
				}
			}
		}
		// cout << st << " : ";for(int i = 1;i<=n;i++)cout << vis[i] << " ";cout << endl;
		return vis;
	};
	vector < int > from1 = eval(1 , graph , -1);
	vector < int > fromn = eval(n , graph , -1);
	vector < int > to1 = eval(1 , igraph , -1);
	vector < int > ton = eval(n , igraph , -1);
	int ans = from1[n] + fromn[1];
	int sayac = 0;
	for(int i = 0;i<m;i++){
		// cout << "edge : " << edge[i][0] << " " << edge[i][1] << " " << edge[i][2] << " " << edge[i][3] << endl;
		int r1 , r2;
		if(is_in_path[i]){
			// cout << "sayac : " << sayac << " " << i << endl;
			sayac++;
			// cout << "special : " << edge[i][0] << " " << edge[i][1] << " " << edge[i][2] << " " << edge[i][3] << endl;
			vector < int > tfrom1 = eval(1 , graph , i);
			// cout << "tfrom1 : ";for(int i = 1;i<=n;i++)cout << tfrom1[i] << " ";cout << endl;
			vector < int > tfromn = eval(n , graph , i);
			// cout << "tfromn : ";for(int i = 1;i<=n;i++)cout << tfromn[i] << " ";cout << endl;
			vector < int > tto1 = eval(1 , igraph , i);
			// cout << "tto1 : ";for(int i = 1;i<=n;i++)cout << tto1[i] << " ";cout << endl;
			vector < int > tton = eval(n , igraph , i);
			// cout << "tton : ";for(int i = 1;i<=n;i++)cout << tton[i] << " ";cout << endl;
			r1 = min(tfrom1[n] , tfrom1[edge[i][1]] + edge[i][2] + tton[edge[i][0]]);//gidis
			r2 = min(tfromn[1] , tfromn[edge[i][1]] + edge[i][2] + tto1[edge[i][0]]);//donus
			// cout << "r : " << r1 << " " << r2 << endl;
		}
		else{
			// cout << "ordinary : " << edge[i][0] << " " << edge[i][1] << " " << edge[i][2] << " " << edge[i][3] << endl;
			r1 = min(from1[n] , from1[edge[i][1]] + edge[i][2] + ton[edge[i][0]]);//gidis
			r2 = min(fromn[1] , fromn[edge[i][1]] + edge[i][2] + to1[edge[i][0]]);//donus
			// cout << "r : " << r1 << " " << r2 << endl;
		}
		// cout << "######" << endl;
		ans = min(ans , edge[i][3] + r1 + r2);
	}
	cout << (ans >= inf ? -1 : ans) << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 49 ms 468 KB Output is correct
4 Correct 50 ms 604 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 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 348 KB Output is correct
10 Correct 38 ms 348 KB Output is correct
11 Correct 51 ms 344 KB Output is correct
12 Incorrect 56 ms 580 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 6816 KB Output is correct
2 Incorrect 367 ms 6484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 348 KB Output is correct
2 Correct 7 ms 460 KB Output is correct
3 Correct 254 ms 5452 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 269 ms 6576 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 137 ms 6888 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 49 ms 468 KB Output is correct
4 Correct 50 ms 604 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 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 348 KB Output is correct
10 Correct 38 ms 348 KB Output is correct
11 Correct 51 ms 344 KB Output is correct
12 Incorrect 56 ms 580 KB Output isn't correct
13 Halted 0 ms 0 KB -