제출 #717478

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
717478		1ne	Swapping Cities (APIO20_swap)	C++14	0 / 100	240 ms	524288 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);
	}	
	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;
					q.push(v);
				}	
			}	
		}	
	}
	sort(edges.begin(),edges.end());
}

int getMinimumFuelCapacity(int X, int Y) {
	DSU st(n);
	int cur = 0;
	vector<int>deg(n,0);
	bool cyc = false;
	for (auto x:d){
		while(cur < m && edges[cur].d <= x){
			int u = st.findsets(X);
			int v = st.findsets(Y);
			if (edges[cur].x != X && edges[cur].y != X && st.findsets(edges[cur].x) == u && st.findsets(edges[cur].y) == u){
				cyc = true;
			}
			if (edges[cur].x != Y && edges[cur].y != Y && st.findsets(edges[cur].x) == v && st.findsets(edges[cur].y) == v){
				cyc = true;
			}
			int p = st.unionset(edges[cur].x,edges[cur].y);
			u = st.findsets(X);
			v = st.findsets(Y);
			if (p){
				deg[edges[cur].x]++;
				deg[edges[cur].y]++;
			}	
			if (u == v && ((st.sz[u] >= dist[X][Y] + deg[X] + deg[Y]) || cyc)){
				//cout<<st.sz[u]<<" "<<dist[X][Y]<<" "<<deg[X]<<" "<<deg[Y]<<'\n';
				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