oj.uz

답안 #954361

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954361 2024-03-27T16:47:54 Z amirhoseinfar1385 자매 도시 (APIO20_swap) C++17
0 / 100
 2000 ms 25224 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],val[maxn];
	vector<int>allv[maxn];
	dsu(){
		for(int i=0;i<maxn;i++){
			par[i]=i;
			val[i]=inf;
			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);
			}
			val[rootu]=min(val[rootu],val[rootv]);
			if(val[rootu]<inf){
				for(auto x:allv[rootu]){
					mainres[x]=min(mainres[x],val[rootu]);
				}
				allv[rootu].clear();
			}
			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();
		val[u]=min(w,val[u]);
	}
}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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 5 ms 9668 KB Output is correct
4 Correct 7 ms 9972 KB Output is correct
5 Correct 5 ms 10012 KB Output is correct
6 Correct 6 ms 9820 KB Output is correct
7 Correct 6 ms 9820 KB Output is correct
8 Correct 5 ms 9820 KB Output is correct
9 Correct 59 ms 20476 KB Output is correct
10 Correct 86 ms 24676 KB Output is correct
11 Correct 117 ms 24300 KB Output is correct
12 Correct 139 ms 25224 KB Output is correct
13 Correct 77 ms 22192 KB Output is correct
14 Execution timed out 2009 ms 23548 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 5 ms 9668 KB Output is correct
4 Correct 7 ms 9972 KB Output is correct
5 Correct 5 ms 10012 KB Output is correct
6 Correct 6 ms 9820 KB Output is correct
7 Correct 6 ms 9820 KB Output is correct
8 Correct 5 ms 9820 KB Output is correct
9 Correct 6 ms 9820 KB Output is correct
10 Correct 6 ms 9864 KB Output is correct
11 Correct 6 ms 9820 KB Output is correct
12 Correct 6 ms 9816 KB Output is correct
13 Correct 6 ms 9820 KB Output is correct
14 Correct 5 ms 9820 KB Output is correct
15 Incorrect 6 ms 9820 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9820 KB Output is correct
2 Correct 5 ms 9816 KB Output is correct
3 Correct 5 ms 9820 KB Output is correct
4 Correct 5 ms 9668 KB Output is correct
5 Correct 7 ms 9972 KB Output is correct
6 Correct 5 ms 10012 KB Output is correct
7 Correct 6 ms 9820 KB Output is correct
8 Correct 6 ms 9820 KB Output is correct
9 Correct 5 ms 9820 KB Output is correct
10 Correct 59 ms 20476 KB Output is correct
11 Correct 86 ms 24676 KB Output is correct
12 Correct 117 ms 24300 KB Output is correct
13 Correct 139 ms 25224 KB Output is correct
14 Correct 77 ms 22192 KB Output is correct
15 Correct 6 ms 9864 KB Output is correct
16 Correct 6 ms 9820 KB Output is correct
17 Correct 6 ms 9816 KB Output is correct
18 Correct 6 ms 9820 KB Output is correct
19 Correct 5 ms 9820 KB Output is correct
20 Incorrect 6 ms 9820 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 5 ms 9668 KB Output is correct
4 Correct 7 ms 9972 KB Output is correct
5 Correct 5 ms 10012 KB Output is correct
6 Correct 6 ms 9820 KB Output is correct
7 Correct 6 ms 9820 KB Output is correct
8 Correct 5 ms 9820 KB Output is correct
9 Correct 59 ms 20476 KB Output is correct
10 Correct 86 ms 24676 KB Output is correct
11 Correct 117 ms 24300 KB Output is correct
12 Correct 139 ms 25224 KB Output is correct
13 Correct 77 ms 22192 KB Output is correct
14 Execution timed out 2009 ms 23548 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9820 KB Output is correct
2 Correct 5 ms 9816 KB Output is correct
3 Correct 5 ms 9820 KB Output is correct
4 Correct 5 ms 9668 KB Output is correct
5 Correct 7 ms 9972 KB Output is correct
6 Correct 5 ms 10012 KB Output is correct
7 Correct 6 ms 9820 KB Output is correct
8 Correct 6 ms 9820 KB Output is correct
9 Correct 5 ms 9820 KB Output is correct
10 Correct 59 ms 20476 KB Output is correct
11 Correct 86 ms 24676 KB Output is correct
12 Correct 117 ms 24300 KB Output is correct
13 Correct 139 ms 25224 KB Output is correct
14 Correct 77 ms 22192 KB Output is correct
15 Execution timed out 2009 ms 23548 KB Time limit exceeded
16 Halted 0 ms 0 KB -