oj.uz

Submission #349994

# Submission time Handle Problem Language Result Execution time Memory
349994 2021-01-18T19:50:49 Z Kerim Swapping Cities (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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -