제출 #965975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
965975		pcc	Swapping Cities (APIO20_swap)	C++17	0 / 100	9 ms	14680 KiB

swap

#include "swap.h"

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

#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 2e5+10;

vector<int> v;
int N,M;
vector<pair<int,pii>> edges;

void init(int NN, int MM,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	N = NN,M = MM;
	for(int i = 0;i<M;i++){
		edges.push_back(make_pair(W[i],pii(U[i],V[i])));
	}
	sort(edges.begin(),edges.end());
	return;
}

namespace BIS{
	vector<int> paths[mxn];
	int dp[mxn];
	queue<int> q;
	int deg[mxn];

	void bfs(int s,int t,int tag){
		q.push(s);
		dp[s] |= tag;
		while(!q.empty()){
			auto now = q.front();
			q.pop();
			if(now == t)continue;
			for(auto nxt:paths[now]){
				if(dp[nxt]&tag)continue;
				dp[nxt]|=tag;
				q.push(nxt);
			}
		}
		return;
	}

	int cnt[mxn];
	bool check(int id,int s,int t){
		memset(dp,0,sizeof(dp));
		memset(deg,0,sizeof(deg));
		memset(cnt,0,sizeof(cnt));
		for(int i = 0;i<N;i++)paths[i].clear();
		for(int i = 0;i<=min(M-1,id);i++){
			paths[edges[i].sc.fs].push_back(edges[i].sc.sc);
			paths[edges[i].sc.sc].push_back(edges[i].sc.fs);
		}
		bfs(s,N,1);
		if(dp[t] != 1)return false;
		for(int i = 0;i<N;i++){
			if(dp[i]){
				for(auto nxt:paths[i])deg[nxt]++;
			}
		}
		for(int i = 0;i<N;i++){
			cnt[deg[i]]++;
		}
		if(*max_element(cnt+3,cnt+N) == 0&&cnt[1] == 2)return false;
		return true;
	}
}

int getMinimumFuelCapacity(int X, int Y) {
	int l = 0,r = M;
	while(l != r){
		int mid = (l+r)>>1;
		if(BIS::check(mid,X,Y))r = mid;
		else l = mid+1;
		//cout<<X<<' '<<Y<<' '<<edges[mid].fs<<":"<<BIS::check(mid,X,Y)<<endl;
	}
	if(r>=M)return -1;
	return edges[l].fs;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27