제출 #717469

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
717469		1ne	자매 도시 (APIO20_swap)	C++14	0 / 100	0 ms	212 KiB

swap

#include "swap.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;
int n,m;       
vector<int>d;
struct edge{
  int x,y,d;
  bool operator < (const edge &P)const{
  	return d < P.d;
  }
};
struct DSU{
	vector<int>parent,sz;
	DSU(int n){
		parent.resize(n);
		sz.resize(n,1);
		iota(parent.begin(),parent.end(),0);
	}
	int findsets(int v){
		if (v == parent[v]){
			return v;
		}
		parent[v] = findsets(parent[v]);
		return parent[v];
	}
	bool unionset(int u,int v){
		u = findsets(u);
		v = findsets(v);
		if (u == v){
			return false;
		}
		if (sz[v] > sz[u]){
			swap(u,v);
		}
		parent[v] = u;
		sz[u]+=sz[v];
		return true;
	};
};
vector<vector<int>>dist;
vector<edge>edges;
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = N;
	m = M;
	d = W;
	dist.resize(n,vector<int>(n,1e6 + 1));
	sort(d.begin(),d.end());
	d.erase(unique(d.begin(),d.end()),d.end());
	vector<vector<int>>adj(n);
	for (int i = 0;i<m;++i){
		edges.push_back({U[i],V[i],W[i]});
		adj[U[i]].push_back(i);
		adj[V[i]].push_back(i);
	}	
	sort(edges.begin(),edges.end());
	for (int i  = 0;i<n;++i){       
		queue<int>q;
		q.push(i);
		dist[i][i] = 0;
		while(!q.empty()){
			int u = q.front();
			q.pop();
			for (auto x:adj[u]){
				int v = edges[x].x ^ edges[x].y ^ u;
				if (dist[i][v] > dist[i][u] + 1){
					dist[i][v] = dist[i][u] + 1;
				}
			}	
		}
	}
}

int getMinimumFuelCapacity(int X, int Y) {
	DSU st(n);
	int cur = 0;
	for (auto x:d){
		while(cur < m && edges[cur].d <= x){
			st.unionset(edges[cur].x,edges[cur].y);
			int u = st.findsets(X);
			int v = st.findsets(Y);
			if (u == v && st.sz[u] > dist[u][v]){
				return x;
			}
			++cur;
		}
	}
	return -1;
}
                               

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