oj.uz

Submission #893554

# Submission time Handle Problem Language Result Execution time Memory
893554 2023-12-27T06:59:08 Z vjudge1 Evacuation plan (IZhO18_plan) C++17
22 / 100
 1371 ms 107440 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]);
		}
	}
	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 2 ms 8708 KB Output is correct
2 Correct 1024 ms 25180 KB Output is correct
3 Correct 1027 ms 25308 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1075 ms 25300 KB Output is correct
6 Correct 1004 ms 25432 KB Output is correct
7 Correct 3 ms 10584 KB Output is correct
8 Correct 3 ms 10808 KB Output is correct
9 Correct 1335 ms 25264 KB Output is correct
10 Correct 1014 ms 25300 KB Output is correct
11 Correct 1366 ms 25260 KB Output is correct
12 Correct 1010 ms 25304 KB Output is correct
13 Correct 1245 ms 25260 KB Output is correct
14 Correct 1366 ms 25268 KB Output is correct
15 Correct 1371 ms 25428 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8708 KB Output is correct
2 Correct 1024 ms 25180 KB Output is correct
3 Correct 1027 ms 25308 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1075 ms 25300 KB Output is correct
6 Correct 1004 ms 25432 KB Output is correct
7 Correct 3 ms 10584 KB Output is correct
8 Correct 3 ms 10808 KB Output is correct
9 Correct 1335 ms 25264 KB Output is correct
10 Correct 1014 ms 25300 KB Output is correct
11 Correct 1366 ms 25260 KB Output is correct
12 Correct 1010 ms 25304 KB Output is correct
13 Correct 1245 ms 25260 KB Output is correct
14 Correct 1366 ms 25268 KB Output is correct
15 Correct 1371 ms 25428 KB Output is correct
16 Runtime error 98 ms 93104 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 10584 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 10588 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 10788 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 158 ms 107440 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 8708 KB Output is correct
2 Correct 1024 ms 25180 KB Output is correct
3 Correct 1027 ms 25308 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1075 ms 25300 KB Output is correct
6 Correct 1004 ms 25432 KB Output is correct
7 Correct 3 ms 10584 KB Output is correct
8 Correct 3 ms 10808 KB Output is correct
9 Correct 1335 ms 25264 KB Output is correct
10 Correct 1014 ms 25300 KB Output is correct
11 Correct 1366 ms 25260 KB Output is correct
12 Correct 1010 ms 25304 KB Output is correct
13 Correct 1245 ms 25260 KB Output is correct
14 Correct 1366 ms 25268 KB Output is correct
15 Correct 1371 ms 25428 KB Output is correct
16 Runtime error 98 ms 93104 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -