oj.uz

답안 #954338

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954338 2024-03-27T16:10:29 Z amirhoseinfar1385 자매 도시 (APIO20_swap) C++17
0 / 100
 2000 ms 22200 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[rootu]=rootv;
			if((int)allv[rootu].size()<(int)allv[rootv].size()){
				swap(allv[rootu],allv[rootv]);
			}
			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(i,alle[i].w);
			}
		}else{
			av=min(alle[i].w,av);
		}
	}
}
int mx;
void dfsres(int u,int had,int par=-1,int len=0){
	if(had==u){
		mx=max(len,mx);
		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=min(mx,min(av,min(mainres[X],mainres[Y])));
  if(ret>=inf){
  	return -1;
  }
  return ret;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 5 ms 9820 KB Output is correct
4 Correct 5 ms 9820 KB Output is correct
5 Correct 5 ms 9976 KB Output is correct
6 Correct 5 ms 9820 KB Output is correct
7 Correct 5 ms 9960 KB Output is correct
8 Correct 5 ms 9816 KB Output is correct
9 Correct 50 ms 17840 KB Output is correct
10 Correct 76 ms 21668 KB Output is correct
11 Correct 78 ms 21452 KB Output is correct
12 Correct 74 ms 22200 KB Output is correct
13 Correct 59 ms 21688 KB Output is correct
14 Execution timed out 2056 ms 20592 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 9820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 5 ms 9820 KB Output is correct
4 Correct 5 ms 9820 KB Output is correct
5 Correct 5 ms 9976 KB Output is correct
6 Correct 5 ms 9820 KB Output is correct
7 Correct 5 ms 9960 KB Output is correct
8 Correct 5 ms 9816 KB Output is correct
9 Correct 50 ms 17840 KB Output is correct
10 Correct 76 ms 21668 KB Output is correct
11 Correct 78 ms 21452 KB Output is correct
12 Correct 74 ms 22200 KB Output is correct
13 Correct 59 ms 21688 KB Output is correct
14 Execution timed out 2056 ms 20592 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 9820 KB Output isn't correct
2 Halted 0 ms 0 KB -