oj.uz

Submission #1069411

# Submission time Handle Problem Language Result Execution time Memory
1069411 2024-08-21T21:47:32 Z pawned Swapping Cities (APIO20_swap) C++17
37 / 100
 2000 ms 25172 KB 
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

#include "swap.h"

const int MAX = 1e5 + 5;

int N, M;

vector<ii> adj[MAX];	// {vertex, dist}

vi wt;

void init(int N_g, int M_g, vi U_g, vi V_g, vi W_g) {
	N = N_g;
	M = M_g;
	for (int i = 0; i < M; i++) {
		adj[U_g[i]].pb({V_g[i], W_g[i]});
		adj[V_g[i]].pb({U_g[i], W_g[i]});
		wt.pb(W_g[i]);
	}
	sort(wt.begin(), wt.end());
}

bool check(int cut, int X, int Y) {
	vi adjc[N];
	for (int i = 0; i < N; i++) {
		for (ii p : adj[i]) {
			if (p.se <= cut)
				adjc[i].pb(p.fi);
		}
	}
	vector<bool> vis(N, false);
	queue<int> q;
	q.push(X);
	vis[X] = true;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int y : adjc[x]) {
			if (!vis[y]) {
				q.push(y);
				vis[y] = true;
			}
		}
	}
	if (!vis[Y])
		return false;
	vi adjd[N];
	for (int i = 0; i < N; i++) {
		if (!vis[i])
			continue;
		for (int x : adjc[i]) {
			if (vis[x])
				adjd[i].pb(x);
		}
	}
	int cnte = 0;	// number of edges
	int sz = 0;	// number of vertices
	for (int i = 0; i < N; i++) {
		cnte += adjd[i].size();
		if (adjd[i].size() >= 1)
			sz++;
	}
	cnte /= 2;
//	cout<<"sz, cnte: "<<sz<<" "<<cnte<<endl;
	if (cnte > sz - 1)	// has a cycle
		return true;
	for (int i = 0; i < N; i++) {
		if (adjd[i].size() >= 3)
			return true;
	}
	return false;
}

int getMinimumFuelCapacity(int X, int Y) {
//	cout<<check(3, X, Y)<<endl;
	int low = 0;
	int high = M - 1;
	int ans = -1;	// minimum so can pass
	while (low <= high) {	// false, false, false, true, true, true
		int mid = (low + high) / 2;
		if (check(wt[mid], X, Y)) {
			ans = mid;
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
	if (ans != -1)
		return wt[ans];
	return -1;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2848 KB Output is correct
5 Correct 3 ms 2908 KB Output is correct
6 Correct 3 ms 2924 KB Output is correct
7 Correct 4 ms 2908 KB Output is correct
8 Correct 4 ms 2908 KB Output is correct
9 Correct 178 ms 14872 KB Output is correct
10 Correct 449 ms 17760 KB Output is correct
11 Correct 563 ms 17604 KB Output is correct
12 Correct 637 ms 18228 KB Output is correct
13 Correct 856 ms 18228 KB Output is correct
14 Execution timed out 2072 ms 15012 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Execution timed out 2041 ms 21420 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2848 KB Output is correct
5 Correct 3 ms 2908 KB Output is correct
6 Correct 3 ms 2924 KB Output is correct
7 Correct 4 ms 2908 KB Output is correct
8 Correct 4 ms 2908 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 6 ms 2904 KB Output is correct
11 Correct 4 ms 2908 KB Output is correct
12 Correct 4 ms 2908 KB Output is correct
13 Correct 3 ms 2788 KB Output is correct
14 Correct 4 ms 2908 KB Output is correct
15 Correct 4 ms 2796 KB Output is correct
16 Correct 4 ms 2908 KB Output is correct
17 Correct 6 ms 2908 KB Output is correct
18 Correct 5 ms 2908 KB Output is correct
19 Correct 5 ms 2904 KB Output is correct
20 Correct 4 ms 2936 KB Output is correct
21 Correct 4 ms 2908 KB Output is correct
22 Correct 4 ms 2908 KB Output is correct
23 Correct 4 ms 2652 KB Output is correct
24 Correct 6 ms 2904 KB Output is correct
25 Correct 6 ms 2908 KB Output is correct
26 Correct 5 ms 2908 KB Output is correct
27 Correct 4 ms 2908 KB Output is correct
28 Correct 6 ms 2908 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2848 KB Output is correct
6 Correct 3 ms 2908 KB Output is correct
7 Correct 3 ms 2924 KB Output is correct
8 Correct 4 ms 2908 KB Output is correct
9 Correct 4 ms 2908 KB Output is correct
10 Correct 178 ms 14872 KB Output is correct
11 Correct 449 ms 17760 KB Output is correct
12 Correct 563 ms 17604 KB Output is correct
13 Correct 637 ms 18228 KB Output is correct
14 Correct 856 ms 18228 KB Output is correct
15 Correct 6 ms 2904 KB Output is correct
16 Correct 4 ms 2908 KB Output is correct
17 Correct 4 ms 2908 KB Output is correct
18 Correct 3 ms 2788 KB Output is correct
19 Correct 4 ms 2908 KB Output is correct
20 Correct 4 ms 2796 KB Output is correct
21 Correct 4 ms 2908 KB Output is correct
22 Correct 6 ms 2908 KB Output is correct
23 Correct 5 ms 2908 KB Output is correct
24 Correct 5 ms 2904 KB Output is correct
25 Correct 4 ms 2936 KB Output is correct
26 Correct 4 ms 2908 KB Output is correct
27 Correct 4 ms 2908 KB Output is correct
28 Correct 4 ms 2652 KB Output is correct
29 Correct 6 ms 2904 KB Output is correct
30 Correct 6 ms 2908 KB Output is correct
31 Correct 5 ms 2908 KB Output is correct
32 Correct 4 ms 2908 KB Output is correct
33 Correct 6 ms 2908 KB Output is correct
34 Correct 19 ms 4696 KB Output is correct
35 Correct 586 ms 18228 KB Output is correct
36 Correct 516 ms 18484 KB Output is correct
37 Correct 519 ms 18268 KB Output is correct
38 Correct 584 ms 18200 KB Output is correct
39 Correct 519 ms 17992 KB Output is correct
40 Correct 547 ms 17080 KB Output is correct
41 Correct 577 ms 18484 KB Output is correct
42 Correct 541 ms 18452 KB Output is correct
43 Correct 612 ms 18224 KB Output is correct
44 Correct 618 ms 18740 KB Output is correct
45 Correct 849 ms 18112 KB Output is correct
46 Correct 538 ms 18444 KB Output is correct
47 Correct 672 ms 18480 KB Output is correct
48 Correct 786 ms 18808 KB Output is correct
49 Correct 93 ms 11972 KB Output is correct
50 Correct 152 ms 9540 KB Output is correct
51 Correct 595 ms 15460 KB Output is correct
52 Correct 942 ms 21120 KB Output is correct
53 Correct 822 ms 21324 KB Output is correct
54 Correct 872 ms 22428 KB Output is correct
55 Correct 581 ms 20276 KB Output is correct
56 Correct 1266 ms 25172 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2848 KB Output is correct
5 Correct 3 ms 2908 KB Output is correct
6 Correct 3 ms 2924 KB Output is correct
7 Correct 4 ms 2908 KB Output is correct
8 Correct 4 ms 2908 KB Output is correct
9 Correct 178 ms 14872 KB Output is correct
10 Correct 449 ms 17760 KB Output is correct
11 Correct 563 ms 17604 KB Output is correct
12 Correct 637 ms 18228 KB Output is correct
13 Correct 856 ms 18228 KB Output is correct
14 Execution timed out 2072 ms 15012 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2848 KB Output is correct
6 Correct 3 ms 2908 KB Output is correct
7 Correct 3 ms 2924 KB Output is correct
8 Correct 4 ms 2908 KB Output is correct
9 Correct 4 ms 2908 KB Output is correct
10 Correct 178 ms 14872 KB Output is correct
11 Correct 449 ms 17760 KB Output is correct
12 Correct 563 ms 17604 KB Output is correct
13 Correct 637 ms 18228 KB Output is correct
14 Correct 856 ms 18228 KB Output is correct
15 Execution timed out 2072 ms 15012 KB Time limit exceeded
16 Halted 0 ms 0 KB -