oj.uz

답안 #954337

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954337 2024-03-27T16:09:20 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=min(mainres[X],mainres[Y]);
  dfsres(X,Y);
  long long ret=max(mx,av);
  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 9912 KB Output is correct
6 Correct 5 ms 9816 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 5 ms 9816 KB Output is correct
9 Correct 48 ms 17804 KB Output is correct
10 Correct 67 ms 21736 KB Output is correct
11 Correct 75 ms 21548 KB Output is correct
12 Correct 80 ms 22200 KB Output is correct
13 Correct 61 ms 21692 KB Output is correct
14 Execution timed out 2057 ms 20920 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 2019 ms 18632 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 9912 KB Output is correct
6 Correct 5 ms 9816 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 5 ms 9816 KB Output is correct
9 Incorrect 5 ms 10072 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 10072 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 9912 KB Output is correct
6 Correct 5 ms 9816 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 5 ms 9816 KB Output is correct
9 Correct 48 ms 17804 KB Output is correct
10 Correct 67 ms 21736 KB Output is correct
11 Correct 75 ms 21548 KB Output is correct
12 Correct 80 ms 22200 KB Output is correct
13 Correct 61 ms 21692 KB Output is correct
14 Execution timed out 2057 ms 20920 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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