oj.uz

답안 #1069396

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1069396 2024-08-21T21:26:07 Z pawned 자매 도시 (APIO20_swap) C++17
0 / 100
 2000 ms 19724 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}

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]});
	}
}

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;
	int cnte = 0;	// number of edges
	int sz = 0;	// number of vertices
	for (int i = 0; i < N; i++) {
		cnte += adjc[i].size();
		if (adjc[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 (adjc[i].size() >= 3)
			return true;
	}
	return false;
}

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

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 7 ms 2856 KB Output is correct
6 Correct 8 ms 2884 KB Output is correct
7 Correct 8 ms 2904 KB Output is correct
8 Correct 9 ms 2652 KB Output is correct
9 Correct 357 ms 12368 KB Output is correct
10 Correct 832 ms 14220 KB Output is correct
11 Correct 1014 ms 13816 KB Output is correct
12 Correct 1055 ms 14524 KB Output is correct
13 Correct 1202 ms 14516 KB Output is correct
14 Execution timed out 2025 ms 12468 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Execution timed out 2058 ms 19724 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 7 ms 2856 KB Output is correct
6 Correct 8 ms 2884 KB Output is correct
7 Correct 8 ms 2904 KB Output is correct
8 Correct 9 ms 2652 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 7 ms 2648 KB Output is correct
11 Correct 8 ms 2796 KB Output is correct
12 Correct 15 ms 2896 KB Output is correct
13 Correct 7 ms 2652 KB Output is correct
14 Correct 7 ms 2876 KB Output is correct
15 Incorrect 8 ms 2652 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 4 ms 2652 KB Output is correct
6 Correct 7 ms 2856 KB Output is correct
7 Correct 8 ms 2884 KB Output is correct
8 Correct 8 ms 2904 KB Output is correct
9 Correct 9 ms 2652 KB Output is correct
10 Correct 357 ms 12368 KB Output is correct
11 Correct 832 ms 14220 KB Output is correct
12 Correct 1014 ms 13816 KB Output is correct
13 Correct 1055 ms 14524 KB Output is correct
14 Correct 1202 ms 14516 KB Output is correct
15 Correct 7 ms 2648 KB Output is correct
16 Correct 8 ms 2796 KB Output is correct
17 Correct 15 ms 2896 KB Output is correct
18 Correct 7 ms 2652 KB Output is correct
19 Correct 7 ms 2876 KB Output is correct
20 Incorrect 8 ms 2652 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 7 ms 2856 KB Output is correct
6 Correct 8 ms 2884 KB Output is correct
7 Correct 8 ms 2904 KB Output is correct
8 Correct 9 ms 2652 KB Output is correct
9 Correct 357 ms 12368 KB Output is correct
10 Correct 832 ms 14220 KB Output is correct
11 Correct 1014 ms 13816 KB Output is correct
12 Correct 1055 ms 14524 KB Output is correct
13 Correct 1202 ms 14516 KB Output is correct
14 Execution timed out 2025 ms 12468 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 4 ms 2652 KB Output is correct
6 Correct 7 ms 2856 KB Output is correct
7 Correct 8 ms 2884 KB Output is correct
8 Correct 8 ms 2904 KB Output is correct
9 Correct 9 ms 2652 KB Output is correct
10 Correct 357 ms 12368 KB Output is correct
11 Correct 832 ms 14220 KB Output is correct
12 Correct 1014 ms 13816 KB Output is correct
13 Correct 1055 ms 14524 KB Output is correct
14 Correct 1202 ms 14516 KB Output is correct
15 Execution timed out 2025 ms 12468 KB Time limit exceeded
16 Halted 0 ms 0 KB -