oj.uz

답안 #1069426

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1069426 2024-08-21T22:05:48 Z pawned 자매 도시 (APIO20_swap) C++17
0 / 100
 107 ms 19564 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;


bool checkm(int cut) {	// minimum weight so has tree from 0
	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(0);
	vis[0] = true;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int y : adjc[x]) {
			if (!vis[y]) {
				q.push(y);
				vis[y] = true;
			}
		}
	}
	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 comp() {
	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 (checkm(wt[mid])) {
			ans = mid;
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
	if (ans != -1)
		return wt[ans];
	return -1;
}

int minv;	// minimum so there's a tree

vi maxw(MAX, -1);

void dfs(int n) {
	for (ii p : adj[n]) {
		if (maxw[p.fi] == -1) {
			maxw[p.fi] = max(maxw[n], p.se);
			dfs(p.fi);
		}
	}
}

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());
	minv = comp();
	maxw[0] = 0;
	dfs(0);
/*	cout<<"minv: "<<minv<<endl;
	cout<<"maxw: ";
	for (int i = 0; i < N; i++) {
		cout<<maxw[i]<<" ";
	}
	cout<<endl;*/
}

int getMinimumFuelCapacity(int X, int Y) {
	if (minv == -1)
		return -1;
	return max(maxw[Y], minv);
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Incorrect 1 ms 3164 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Incorrect 107 ms 19564 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Incorrect 1 ms 3164 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Incorrect 1 ms 3164 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Incorrect 1 ms 3164 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Incorrect 1 ms 3164 KB Output isn't correct
5 Halted 0 ms 0 KB -