oj.uz

답안 #717480

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
717480 2023-04-02T01:14:20 Z 1ne 자매 도시 (APIO20_swap) C++14
0 / 100
 249 ms 524288 KB 
#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);
			bool pos = false;
			if (edges[cur].x != X && edges[cur].y != X && st.findsets(edges[cur].x) == u && st.findsets(edges[cur].y) == u){
				pos = true;
			}
			if (edges[cur].x != Y && edges[cur].y != Y && st.findsets(edges[cur].x) == v && st.findsets(edges[cur].y) == v){
				pos = true;
			}
			int p = st.unionset(edges[cur].x,edges[cur].y);
			if (p && pos){
				cyc = true;
			}
			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.0

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

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 249 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

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

Subtask #6
0 / 27.0

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