oj.uz

Submission #893582

# Submission time Handle Problem Language Result Execution time Memory
893582 2023-12-27T07:14:52 Z vjudge1 Evacuation plan (IZhO18_plan) C++17
22 / 100
 1497 ms 107624 KB 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <fstream>
#include <unordered_map>
using namespace std;

typedef long long ll;
typedef long double ld;

#define all(x) x.begin(),x.end()
#define pb push_back
#define ent "\n"

#define int long long

const int maxn = (int)2e5 + 13;
const ll inf = (long long)1e18 + 20;
const int mod = (int)1e9 + 7;

int n,m,k,q;
vector<pair<int,int>>g[maxn];
int a[maxn];
int dst[maxn];
int dp[2001][2001];

int get(int x,int y,int p){
	
}

void solve(){
	cin >> n >> m ;
	for(int i = 1 ; i <= m ; i++){
		int x,y,w;cin >> x >> y >> w;
		g[x].pb({y,w});
		g[y].pb({x,w});
	}
	cin >> k;
	set<pair<int,int>>s;
	for(int i = 1 ; i <= n ; i ++){
		dst[i] = inf;
	}
	for(int i = 1 ; i <= k ; i ++){
		cin >> a[i];
		s.insert({0,a[i]});
		dst[a[i]] = 0;
	}
	while(s.size()){
		pair<int,int>v = *s.begin();
		s.erase(v);
		for(auto to : g[v.second]){
			int val = dst[v.second] + to.second;
			if(dst[to.first] > val){
				dst[to.first] = val;
				s.insert({val,to.first});
			}
		}
	}
	for(int i = 1 ; i <= n ; i ++){
		dp[i][i] = dst[i];
	}
	for(int i = 1 ; i <= n ; i ++){
		for(auto to : g[i]){
			dp[i][to.first] = min(dp[i][i],dp[to.first][to.first]);
		}
	}
	if(n <= 1000 && m <= 1000 ){
		for(int i = 1 ; i <= n ; i ++){
			for(int j = 1 ; j <= n ; j ++){
				for(int c = 1 ; c <= n ; c ++){
					dp[j][c] = max(min(dp[j][i],dp[i][c]),dp[j][c]);
				}
			}
		}
	}
	cin >> q;
	for(int i = 1 ; i <= q ; i ++){
		int l,r;cin >> l >> r;
		if(q > 0){
			cout << dp[l][r] << ent;
			continue;
		}
		int ans = 0;
		for(int j = 1 ; j <= n ; j ++){
			ans = max(ans,min(dp[j][l],dp[j][r]));
		}
		cout << ans << ent;
	}
}

signed main(){
	// freopen ("hps.in", "r", stdin);
	// freopen ("hps.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	int test = 0;
	while(t --){
	//	cout << "Case " << ++test << ": ";
		solve();
	}
	return 0;
}

Compilation message

plan.cpp: In function 'long long int get(long long int, long long int, long long int)':
plan.cpp:53:1: warning: no return statement in function returning non-void [-Wreturn-type]
   53 | }
      | ^
plan.cpp: In function 'int main()':
plan.cpp:122:6: warning: unused variable 'test' [-Wunused-variable]
  122 |  int test = 0;
      |      ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 1188 ms 25304 KB Output is correct
3 Correct 1087 ms 25304 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1037 ms 25300 KB Output is correct
6 Correct 1136 ms 25284 KB Output is correct
7 Correct 3 ms 10584 KB Output is correct
8 Correct 3 ms 10588 KB Output is correct
9 Correct 1238 ms 25260 KB Output is correct
10 Correct 1109 ms 25292 KB Output is correct
11 Correct 1497 ms 25436 KB Output is correct
12 Correct 1027 ms 25308 KB Output is correct
13 Correct 1134 ms 25176 KB Output is correct
14 Correct 1198 ms 25252 KB Output is correct
15 Correct 1182 ms 25252 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 1188 ms 25304 KB Output is correct
3 Correct 1087 ms 25304 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1037 ms 25300 KB Output is correct
6 Correct 1136 ms 25284 KB Output is correct
7 Correct 3 ms 10584 KB Output is correct
8 Correct 3 ms 10588 KB Output is correct
9 Correct 1238 ms 25260 KB Output is correct
10 Correct 1109 ms 25292 KB Output is correct
11 Correct 1497 ms 25436 KB Output is correct
12 Correct 1027 ms 25308 KB Output is correct
13 Correct 1134 ms 25176 KB Output is correct
14 Correct 1198 ms 25252 KB Output is correct
15 Correct 1182 ms 25252 KB Output is correct
16 Runtime error 102 ms 93272 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10680 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 161 ms 107624 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 1188 ms 25304 KB Output is correct
3 Correct 1087 ms 25304 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1037 ms 25300 KB Output is correct
6 Correct 1136 ms 25284 KB Output is correct
7 Correct 3 ms 10584 KB Output is correct
8 Correct 3 ms 10588 KB Output is correct
9 Correct 1238 ms 25260 KB Output is correct
10 Correct 1109 ms 25292 KB Output is correct
11 Correct 1497 ms 25436 KB Output is correct
12 Correct 1027 ms 25308 KB Output is correct
13 Correct 1134 ms 25176 KB Output is correct
14 Correct 1198 ms 25252 KB Output is correct
15 Correct 1182 ms 25252 KB Output is correct
16 Runtime error 102 ms 93272 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -