oj.uz

Submission #893550

# Submission time Handle Problem Language Result Execution time Memory
893550 2023-12-27T06:55:49 Z vjudge1 Evacuation plan (IZhO18_plan) C++17
22 / 100
 1371 ms 123372 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)1e6 + 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[1001][1001];

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]);
		}
	}
	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;
		cout << dp[l][r] << 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:112:6: warning: unused variable 'test' [-Wunused-variable]
  112 |  int test = 0;
      |      ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 28764 KB Output is correct
2 Correct 1000 ms 35212 KB Output is correct
3 Correct 986 ms 35416 KB Output is correct
4 Correct 6 ms 28764 KB Output is correct
5 Correct 1086 ms 35220 KB Output is correct
6 Correct 968 ms 35188 KB Output is correct
7 Correct 8 ms 30812 KB Output is correct
8 Correct 7 ms 30876 KB Output is correct
9 Correct 1331 ms 35164 KB Output is correct
10 Correct 967 ms 35204 KB Output is correct
11 Correct 1371 ms 35160 KB Output is correct
12 Correct 998 ms 35412 KB Output is correct
13 Correct 1237 ms 35168 KB Output is correct
14 Correct 1330 ms 35164 KB Output is correct
15 Correct 1337 ms 35164 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 28764 KB Output is correct
2 Correct 1000 ms 35212 KB Output is correct
3 Correct 986 ms 35416 KB Output is correct
4 Correct 6 ms 28764 KB Output is correct
5 Correct 1086 ms 35220 KB Output is correct
6 Correct 968 ms 35188 KB Output is correct
7 Correct 8 ms 30812 KB Output is correct
8 Correct 7 ms 30876 KB Output is correct
9 Correct 1331 ms 35164 KB Output is correct
10 Correct 967 ms 35204 KB Output is correct
11 Correct 1371 ms 35160 KB Output is correct
12 Correct 998 ms 35412 KB Output is correct
13 Correct 1237 ms 35168 KB Output is correct
14 Correct 1330 ms 35164 KB Output is correct
15 Correct 1337 ms 35164 KB Output is correct
16 Runtime error 105 ms 109072 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 6 ms 28764 KB Output is correct
2 Correct 6 ms 28760 KB Output is correct
3 Correct 6 ms 28764 KB Output is correct
4 Correct 6 ms 28764 KB Output is correct
5 Correct 6 ms 28764 KB Output is correct
6 Correct 6 ms 28764 KB Output is correct
7 Correct 6 ms 28864 KB Output is correct
8 Correct 6 ms 28764 KB Output is correct
9 Correct 6 ms 28864 KB Output is correct
10 Correct 6 ms 28764 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 176 ms 123372 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 7 ms 28764 KB Output is correct
2 Correct 1000 ms 35212 KB Output is correct
3 Correct 986 ms 35416 KB Output is correct
4 Correct 6 ms 28764 KB Output is correct
5 Correct 1086 ms 35220 KB Output is correct
6 Correct 968 ms 35188 KB Output is correct
7 Correct 8 ms 30812 KB Output is correct
8 Correct 7 ms 30876 KB Output is correct
9 Correct 1331 ms 35164 KB Output is correct
10 Correct 967 ms 35204 KB Output is correct
11 Correct 1371 ms 35160 KB Output is correct
12 Correct 998 ms 35412 KB Output is correct
13 Correct 1237 ms 35168 KB Output is correct
14 Correct 1330 ms 35164 KB Output is correct
15 Correct 1337 ms 35164 KB Output is correct
16 Runtime error 105 ms 109072 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -