oj.uz

답안 #954360

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954360 2024-03-27T16:46:31 Z amirhoseinfar1385 자매 도시 (APIO20_swap) C++17
0 / 100
 2000 ms 26680 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]=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 6 ms 10072 KB Output is correct
4 Correct 7 ms 9824 KB Output is correct
5 Correct 5 ms 9820 KB Output is correct
6 Correct 6 ms 9820 KB Output is correct
7 Correct 6 ms 9916 KB Output is correct
8 Correct 6 ms 9820 KB Output is correct
9 Correct 90 ms 21480 KB Output is correct
10 Correct 90 ms 25952 KB Output is correct
11 Correct 122 ms 25784 KB Output is correct
12 Correct 100 ms 26680 KB Output is correct
13 Correct 71 ms 23468 KB Output is correct
14 Execution timed out 2028 ms 24476 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 2005 ms 20256 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 6 ms 10072 KB Output is correct
4 Correct 7 ms 9824 KB Output is correct
5 Correct 5 ms 9820 KB Output is correct
6 Correct 6 ms 9820 KB Output is correct
7 Correct 6 ms 9916 KB Output is correct
8 Correct 6 ms 9820 KB Output is correct
9 Correct 5 ms 9820 KB Output is correct
10 Correct 6 ms 9996 KB Output is correct
11 Correct 5 ms 9820 KB Output is correct
12 Correct 6 ms 9924 KB Output is correct
13 Correct 6 ms 9820 KB Output is correct
14 Correct 6 ms 9940 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 5 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 6 ms 10072 KB Output is correct
5 Correct 7 ms 9824 KB Output is correct
6 Correct 5 ms 9820 KB Output is correct
7 Correct 6 ms 9820 KB Output is correct
8 Correct 6 ms 9916 KB Output is correct
9 Correct 6 ms 9820 KB Output is correct
10 Correct 90 ms 21480 KB Output is correct
11 Correct 90 ms 25952 KB Output is correct
12 Correct 122 ms 25784 KB Output is correct
13 Correct 100 ms 26680 KB Output is correct
14 Correct 71 ms 23468 KB Output is correct
15 Correct 6 ms 9996 KB Output is correct
16 Correct 5 ms 9820 KB Output is correct
17 Correct 6 ms 9924 KB Output is correct
18 Correct 6 ms 9820 KB Output is correct
19 Correct 6 ms 9940 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 6 ms 10072 KB Output is correct
4 Correct 7 ms 9824 KB Output is correct
5 Correct 5 ms 9820 KB Output is correct
6 Correct 6 ms 9820 KB Output is correct
7 Correct 6 ms 9916 KB Output is correct
8 Correct 6 ms 9820 KB Output is correct
9 Correct 90 ms 21480 KB Output is correct
10 Correct 90 ms 25952 KB Output is correct
11 Correct 122 ms 25784 KB Output is correct
12 Correct 100 ms 26680 KB Output is correct
13 Correct 71 ms 23468 KB Output is correct
14 Execution timed out 2028 ms 24476 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 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 6 ms 10072 KB Output is correct
5 Correct 7 ms 9824 KB Output is correct
6 Correct 5 ms 9820 KB Output is correct
7 Correct 6 ms 9820 KB Output is correct
8 Correct 6 ms 9916 KB Output is correct
9 Correct 6 ms 9820 KB Output is correct
10 Correct 90 ms 21480 KB Output is correct
11 Correct 90 ms 25952 KB Output is correct
12 Correct 122 ms 25784 KB Output is correct
13 Correct 100 ms 26680 KB Output is correct
14 Correct 71 ms 23468 KB Output is correct
15 Execution timed out 2028 ms 24476 KB Time limit exceeded
16 Halted 0 ms 0 KB -