oj.uz

Submission #571538

# Submission time Handle Problem Language Result Execution time Memory
571538 2022-06-02T10:40:55 Z vbee Evacuation plan (IZhO18_plan) C++14
22 / 100
 367 ms 39116 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define ii pair<int,int>
#define vii vector<ii>
#define vi vector<int>
#define fi first
#define se second
#define TASK "evacuationplan"
#define ll long long
#define pll pair<ll, ll>
#define vll vector<ll>
#define vpll vector<pll>
#define pb push_back
#define MASK(i) (1 << (i))
#define BIT(x, i) ((x >> (i)) & 1)
 
using namespace std;

const int oo = 1e9 + 7;
const ll loo = (ll)1e18 + 7; 
const int N = 1e5 + 7;
const int M = 1e3 + 7;
const int LOG = 15;

ll n, m, k, q, adist[M][M], f[MASK(LOG)][16], minidist[N], ans[16][16];
vector<pair<ll, ll> > g[N];
vector<ll> npp;

void minimize(ll &a, ll b){
	if (a > b) a = b;
}

void apsp(int i){
	minidist[i] = oo;
	for (int j = 1; j <= n; j++) adist[i][j] = oo;
	adist[i][i] = 0;
	priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> kew;
	kew.push({0, i});
	while (!kew.empty()){
		auto k = kew.top();
		kew.pop();
		if (k.fi > adist[i][k.se]){
			continue;
		}
		for (auto u : g[k.se]) {
			if (k.fi + u.se < adist[i][u.fi]){
				adist[i][u.fi] = k.fi + u.se;
				kew.push({k.fi + u.se, u.fi});
			}
		}
	}
	for (auto u : npp) minidist[i] = min(minidist[i], adist[i][u]);
	return;
}

vector<pair<ll, ll> > queries;

// bool check(int s, int t, int x){
// 	queue<int> kew;
// }
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	// freopen(TASK".inp", "r", stdin);
	// freopen(TASK".out", "w", stdout);
	cin >> n >> m;
	map<pair<ll, ll>, bool> checkexist;
	for (int i = 1; i <= m; i++){
		ll u, v, w; cin >> u >> v >> w;
		g[u].pb({v, w});
		g[v].pb({u, w});
		checkexist[{u, v}] = checkexist[{v, u}] = true;
	}
	cin >> k;
	for (int i = 1; i <= k; i++) {
		ll x; cin >> x;
		npp.pb(x);
	}
	bool sub12 = true;
	cin >> q;
	while (q--){
		int x, y; cin >> x >> y;
		queries.pb({x, y});
		if (!checkexist[{x, y}]) sub12 = false;
	}
	if (n <= 1000 && m <= 1000 && q <= 1000 && sub12){
		for (int i = 1; i <= n; i++) apsp(i);
		for (int j = 0; j < queries.size(); j++) {
			ll res = 0;
			ll x = queries[j].fi, y = queries[j].se;
			res = min(minidist[x], minidist[y]);
			cout << res << "\n";
		}
	}
	else if (n <= 15 && m <= 200 && q <= 200){
		for (int i = 1; i <= n; i++) apsp(i);
		for (int sta = 0; sta < n; sta++){
			for (int mask = 0; mask < MASK(n); mask++) for (int j = 0; j < n; j++) f[mask][j] = oo;
			f[MASK(sta)][sta] = minidist[sta + 1];
			for (int mask = 0; mask < MASK(n); mask++){
				for (int i = 0; i < n; i++) if (f[mask][i] != oo){
					int id = i + 1;
					for (auto u : g[id]){
						int cur = u.fi - 1;
						if (!BIT(mask, cur)){
							minimize(f[mask | MASK(cur)][cur], min(f[mask][i], minidist[u.fi])); 
						}
					}
				}
			}
			for (int mask = 0; mask < MASK(n); mask++){
				for (int i = 0; i < n; i++) if (f[mask][i] != oo){
					ans[sta + 1][i + 1] = max(ans[sta + 1][i + 1], f[mask][i]);
				}
			}
		}
		for (auto u : queries){
			cout << ans[u.fi][u.se] << "\n";
		}
	}
	return 0;
}

Compilation message

plan.cpp: In function 'int main()':
plan.cpp:88:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for (int j = 0; j < queries.size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 96 ms 10848 KB Output is correct
3 Correct 92 ms 10688 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 101 ms 10768 KB Output is correct
6 Correct 102 ms 10808 KB Output is correct
7 Correct 4 ms 3192 KB Output is correct
8 Correct 4 ms 3156 KB Output is correct
9 Correct 80 ms 10732 KB Output is correct
10 Correct 81 ms 10700 KB Output is correct
11 Correct 81 ms 10704 KB Output is correct
12 Correct 94 ms 10808 KB Output is correct
13 Correct 91 ms 10780 KB Output is correct
14 Correct 97 ms 10764 KB Output is correct
15 Correct 81 ms 10680 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 96 ms 10848 KB Output is correct
3 Correct 92 ms 10688 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 101 ms 10768 KB Output is correct
6 Correct 102 ms 10808 KB Output is correct
7 Correct 4 ms 3192 KB Output is correct
8 Correct 4 ms 3156 KB Output is correct
9 Correct 80 ms 10732 KB Output is correct
10 Correct 81 ms 10700 KB Output is correct
11 Correct 81 ms 10704 KB Output is correct
12 Correct 94 ms 10808 KB Output is correct
13 Correct 91 ms 10780 KB Output is correct
14 Correct 97 ms 10764 KB Output is correct
15 Correct 81 ms 10680 KB Output is correct
16 Incorrect 210 ms 25264 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6868 KB Output is correct
2 Correct 24 ms 6856 KB Output is correct
3 Correct 43 ms 6868 KB Output is correct
4 Correct 112 ms 6740 KB Output is correct
5 Correct 145 ms 6868 KB Output is correct
6 Correct 143 ms 6868 KB Output is correct
7 Correct 143 ms 6848 KB Output is correct
8 Correct 21 ms 6860 KB Output is correct
9 Correct 29 ms 6740 KB Output is correct
10 Correct 152 ms 6852 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 367 ms 39116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 96 ms 10848 KB Output is correct
3 Correct 92 ms 10688 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 101 ms 10768 KB Output is correct
6 Correct 102 ms 10808 KB Output is correct
7 Correct 4 ms 3192 KB Output is correct
8 Correct 4 ms 3156 KB Output is correct
9 Correct 80 ms 10732 KB Output is correct
10 Correct 81 ms 10700 KB Output is correct
11 Correct 81 ms 10704 KB Output is correct
12 Correct 94 ms 10808 KB Output is correct
13 Correct 91 ms 10780 KB Output is correct
14 Correct 97 ms 10764 KB Output is correct
15 Correct 81 ms 10680 KB Output is correct
16 Incorrect 210 ms 25264 KB Output isn't correct
17 Halted 0 ms 0 KB -