oj.uz

답안 #954317

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954317 2024-03-27T15:40:31 Z amirhoseinfar1385 자매 도시 (APIO20_swap) C++17
0 / 100
 2000 ms 16844 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;
vector<yal>alle;
vector<int>adjt[maxn];

struct dsu{
	int par[maxn];
	dsu(){
		for(int i=0;i<maxn;i++){
			par[i]=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;
			return 1;
		}else{
			return 0;
		}
	}
}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<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(adjt[alle[i].u].size()>2||adjt[alle[i].v].size()>2){
				av=min(alle[i].w,av);
			}
		}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=len;
		return ;
	}
	for(auto x:adjt[u]){
		int v=alle[x].getad(u);
		if(v==par){
			continue;
		}
		int fake=len;
		for(auto y:adjt[u]){
			if(y!=x){
				fake=max(fake,alle[y].w);
			}
		}
		dfsres(v,had,u,fake);
	}
}

int getMinimumFuelCapacity(int X, int Y) {
  mx=inf;
  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 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 2 ms 4696 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4952 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 40 ms 12472 KB Output is correct
10 Correct 59 ms 16500 KB Output is correct
11 Correct 68 ms 16116 KB Output is correct
12 Correct 69 ms 16844 KB Output is correct
13 Correct 55 ms 16568 KB Output is correct
14 Execution timed out 2067 ms 15400 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 2 ms 4696 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4952 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 40 ms 12472 KB Output is correct
10 Correct 59 ms 16500 KB Output is correct
11 Correct 68 ms 16116 KB Output is correct
12 Correct 69 ms 16844 KB Output is correct
13 Correct 55 ms 16568 KB Output is correct
14 Execution timed out 2067 ms 15400 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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