oj.uz

답안 #349994

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
349994 2021-01-18T19:50:49 Z Kerim 자매 도시 (APIO20_swap) C++17
0 / 100
 2000 ms 10376 KB 
#include "swap.h"
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
vector<int>u,v,w,ind;
int m,n;
int ata[MAXN],sz[MAXN],cycle[MAXN];
bool cmp(int x,int y){
	return (w[x]<w[y]);	
}
void init(int N, int M,vector<int>U,vector<int> V,vector<int> W) {
	u=U;v=V;w=W;m=M;n=N;
	for(int i=0;i<m;i++)ind.pb(i);
	sort(all(ind),cmp);
}
int tap(int x){
	if(ata[x]==x)return x;
	return ata[x]=tap(ata[x]);	
}
void merge(int x,int y){
	if((x=tap(x))==(y=tap(y))){
		cycle[x]=1;
		return;	
	}
	if(sz[x]<sz[y])swap(x,y);
	sz[x]+=sz[y];ata[y]=x;cycle[x]|=cycle[y];
}
int getMinimumFuelCapacity(int X, int Y){
	for(int i=0;i<n;i++)ata[i]=i,sz[i]=1,cycle[i]=0;
	for(int i=0;i<m;i++){
		merge(u[ind[i]],v[ind[i]]);
		if(tap(X)==tap(Y) and cycle[tap(X)])
			return w[ind[i]];
	}
  	return -1;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 47 ms 5352 KB Output is correct
10 Correct 69 ms 6376 KB Output is correct
11 Correct 74 ms 6376 KB Output is correct
12 Correct 79 ms 6632 KB Output is correct
13 Correct 71 ms 6632 KB Output is correct
14 Execution timed out 2081 ms 5736 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Execution timed out 2066 ms 10376 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Incorrect 1 ms 364 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 47 ms 5352 KB Output is correct
11 Correct 69 ms 6376 KB Output is correct
12 Correct 74 ms 6376 KB Output is correct
13 Correct 79 ms 6632 KB Output is correct
14 Correct 71 ms 6632 KB Output is correct
15 Incorrect 1 ms 364 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 47 ms 5352 KB Output is correct
10 Correct 69 ms 6376 KB Output is correct
11 Correct 74 ms 6376 KB Output is correct
12 Correct 79 ms 6632 KB Output is correct
13 Correct 71 ms 6632 KB Output is correct
14 Execution timed out 2081 ms 5736 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 47 ms 5352 KB Output is correct
11 Correct 69 ms 6376 KB Output is correct
12 Correct 74 ms 6376 KB Output is correct
13 Correct 79 ms 6632 KB Output is correct
14 Correct 71 ms 6632 KB Output is correct
15 Execution timed out 2081 ms 5736 KB Time limit exceeded
16 Halted 0 ms 0 KB -