oj.uz

Submission #954347

# Submission time Handle Problem Language Result Execution time Memory
954347 2024-03-27T16:16:31 Z amirhoseinfar1385 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 25312 KB 
#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
struct yal{
	int u,v,w,vas;
	bool operator <(yal b){
		return w<b.w;
	}
	int getad(int fu){
		return (fu^u^v);
	}
};
const int maxn=100000+10,lg=17;
int n,m,wlca[lg][maxn],inf=1e9+5,mainres[maxn];
vector<yal>alle;
vector<int>adjt[maxn];

struct dsu{
	int par[maxn];
	vector<int>allv[maxn];
	dsu(){
		for(int i=0;i<maxn;i++){
			par[i]=i;
			allv[i].push_back(i);
		}
	};
	int root(int u){
		if(u==par[u]){
			return u;
		}
		return par[u]=root(par[u]);
	}
	int con(int u,int v){
		int rootu=root(u),rootv=root(v);
		if(rootu!=rootv){
			par[rootv]=rootu;
			if((int)allv[rootu].size()<(int)allv[rootv].size()){
				swap(allv[rootu],allv[rootv]);
			}
			for(auto x:allv[rootv]){
				allv[rootu].push_back(x);
			}
			return 1;
		}else{
			return 0;
		}
	}
	void tagh(int u,int w){
		u=root(u);
		for(auto x:allv[u]){
			mainres[x]=min(mainres[x],w);
		}
		allv[u].clear();
	}
}ds;
int av=inf;

void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n=N;
	m=M;
	alle.resize(m);
	for(int i=0;i<maxn;i++){
		mainres[i]=inf;
	}
	for(int i=0;i<m;i++){
		alle[i].u=U[i];
		alle[i].v=V[i];
		alle[i].w=W[i];
	}
	sort(alle.begin(),alle.end());
	for(int i=0;i<m;i++){
		if(ds.con(alle[i].u,alle[i].v)){
			alle[i].vas=1;
			adjt[alle[i].u].push_back(i);
			adjt[alle[i].v].push_back(i);
			if((int)adjt[alle[i].u].size()>2||(int)adjt[alle[i].v].size()>2){
				ds.tagh(alle[i].u,alle[i].w);
			}
		}else{
			ds.tagh(alle[i].u,alle[i].w);
		}
	}
}
int mx;
void dfsres(int u,int had,int par=-1,int len=0){
	if(had==u){
		mx=len;
		return ;
	}
	for(auto x:adjt[u]){
		int v=alle[x].getad(u);
		if(v==par){
			continue;
		}
		dfsres(v,had,u,max(len,alle[x].w));
	}
}

int getMinimumFuelCapacity(int X, int Y) {
  mx=inf;
  dfsres(X,Y);
  long long ret=max(mx,min(mainres[X],mainres[Y]));
  if(ret>=inf){
  	return -1;
  }
  return ret;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 6 ms 9820 KB Output is correct
3 Correct 5 ms 9904 KB Output is correct
4 Correct 6 ms 9820 KB Output is correct
5 Correct 5 ms 9820 KB Output is correct
6 Correct 5 ms 9944 KB Output is correct
7 Correct 6 ms 9820 KB Output is correct
8 Correct 5 ms 9972 KB Output is correct
9 Correct 55 ms 20292 KB Output is correct
10 Correct 91 ms 24860 KB Output is correct
11 Correct 95 ms 24300 KB Output is correct
12 Correct 121 ms 25312 KB Output is correct
13 Correct 64 ms 22376 KB Output is correct
14 Execution timed out 2023 ms 23220 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 6 ms 9820 KB Output is correct
3 Execution timed out 2048 ms 18380 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 6 ms 9820 KB Output is correct
3 Correct 5 ms 9904 KB Output is correct
4 Correct 6 ms 9820 KB Output is correct
5 Correct 5 ms 9820 KB Output is correct
6 Correct 5 ms 9944 KB Output is correct
7 Correct 6 ms 9820 KB Output is correct
8 Correct 5 ms 9972 KB Output is correct
9 Correct 5 ms 9816 KB Output is correct
10 Correct 5 ms 9820 KB Output is correct
11 Incorrect 5 ms 9820 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 6 ms 9820 KB Output is correct
4 Correct 5 ms 9904 KB Output is correct
5 Correct 6 ms 9820 KB Output is correct
6 Correct 5 ms 9820 KB Output is correct
7 Correct 5 ms 9944 KB Output is correct
8 Correct 6 ms 9820 KB Output is correct
9 Correct 5 ms 9972 KB Output is correct
10 Correct 55 ms 20292 KB Output is correct
11 Correct 91 ms 24860 KB Output is correct
12 Correct 95 ms 24300 KB Output is correct
13 Correct 121 ms 25312 KB Output is correct
14 Correct 64 ms 22376 KB Output is correct
15 Correct 5 ms 9820 KB Output is correct
16 Incorrect 5 ms 9820 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 6 ms 9820 KB Output is correct
3 Correct 5 ms 9904 KB Output is correct
4 Correct 6 ms 9820 KB Output is correct
5 Correct 5 ms 9820 KB Output is correct
6 Correct 5 ms 9944 KB Output is correct
7 Correct 6 ms 9820 KB Output is correct
8 Correct 5 ms 9972 KB Output is correct
9 Correct 55 ms 20292 KB Output is correct
10 Correct 91 ms 24860 KB Output is correct
11 Correct 95 ms 24300 KB Output is correct
12 Correct 121 ms 25312 KB Output is correct
13 Correct 64 ms 22376 KB Output is correct
14 Execution timed out 2023 ms 23220 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 6 ms 9820 KB Output is correct
4 Correct 5 ms 9904 KB Output is correct
5 Correct 6 ms 9820 KB Output is correct
6 Correct 5 ms 9820 KB Output is correct
7 Correct 5 ms 9944 KB Output is correct
8 Correct 6 ms 9820 KB Output is correct
9 Correct 5 ms 9972 KB Output is correct
10 Correct 55 ms 20292 KB Output is correct
11 Correct 91 ms 24860 KB Output is correct
12 Correct 95 ms 24300 KB Output is correct
13 Correct 121 ms 25312 KB Output is correct
14 Correct 64 ms 22376 KB Output is correct
15 Execution timed out 2023 ms 23220 KB Time limit exceeded
16 Halted 0 ms 0 KB -