제출 #965747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
965747		pcc	자매 도시 (APIO20_swap)	C++17	0 / 100	2029 ms	15480 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 = 1e5+10;

vector<int> v;
int arr[mxn];
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)){
					dp[nxt]|=tag;
					q.push(nxt);
				}
			}
		}
		return;
	}

	bool check(int id,int s,int t){
		memset(dp,0,sizeof(dp));
		memset(deg,0,sizeof(deg));
		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,t,1);
		bfs(t,s,2);
		if(dp[s] != 3||dp[t] != 3)return false;
		for(int i = 0;i<N;i++){
			if(dp[i] == 3){
				for(auto nxt:paths[i])deg[nxt]++;
			}
		}
		bool flag = false;
		for(int i = 0;i<N;i++){
			if(dp[i] == 3&&i != s&&i != t&&deg[i] != 2)flag = true;
		}
		if(deg[s] != 1||deg[t] != 1)flag = true;
		if(paths[s].size()>=3||paths[t].size()>=3)flag = true;
		return flag;
	}
}

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