oj.uz

답안 #954365

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954365 2024-03-27T17:00:07 Z amirhoseinfar1385 자매 도시 (APIO20_swap) C++17
6 / 100
 282 ms 46524 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],lca[lg][maxn],inf=1e9+5,mainres[maxn],timea;
vector<yal>alle;
vector<int>adjt[maxn];
pair<int,int>stf[maxn];

bool zird(int u,int v){
	return stf[v].first<=stf[u].first&&stf[v].second>=stf[u].second;
}

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 w){
		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);
			}
			if(val[rootu]<inf||val[rootv]<inf){
				val[rootu]=w;
			}
			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 dfs(int u=1,int par=-1){
	timea++;
	stf[u].first=timea;
	for(auto x:adjt[u]){
		int v=alle[x].getad(u);
		if(v==par){
			continue;
		}
		wlca[0][v]=alle[x].w;
		lca[0][v]=u;
		dfs(v,u);
	}
	stf[u].second=timea;
}

void callca(){
	for(int i=1;i<lg;i++){
		for(int j=1;j<=n;j++){
			lca[i][j]=lca[i-1][lca[i-1][j]];
			wlca[i][j]=max(wlca[i-1][j],wlca[i-1][lca[i-1][j]]);
		}
	}
}

int getlca(int u,int v){
	if(zird(u,v)){
		return v;
	}
	if(zird(v,u)){
		return u;
	}
	for(int i=lg-1;i>=0;i--){
		if(lca[i][u]!=0&&zird(v,lca[i][u])==0){
			u=lca[i][u];
		}
	}
	return lca[0][u];
}

int getwlca(int u,int v){
	if(u==v){
		return 0;
	}
	int ret=0;
	for(int i=lg-1;i>=0;i--){
		if(lca[i][u]!=0&&zird(v,lca[i][u])==0){
			ret=max(ret,wlca[i][u]);
			u=lca[i][u];
		}
	}
	ret=max(ret,wlca[0][u]);
	return ret;
}

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].w)){
			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);
		}
	}
	dfs();
	callca();
}
int mx;
void dfsres(int u,int v){
	int uv=getlca(u,v);
	mx=max(getwlca(u,uv),getwlca(v,uv));
}

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
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 22108 KB Output is correct
2 Correct 8 ms 22108 KB Output is correct
3 Correct 8 ms 22108 KB Output is correct
4 Correct 9 ms 22048 KB Output is correct
5 Correct 8 ms 22108 KB Output is correct
6 Correct 8 ms 22340 KB Output is correct
7 Correct 8 ms 22108 KB Output is correct
8 Correct 8 ms 22364 KB Output is correct
9 Correct 91 ms 35212 KB Output is correct
10 Correct 86 ms 38560 KB Output is correct
11 Correct 84 ms 37116 KB Output is correct
12 Correct 106 ms 37744 KB Output is correct
13 Correct 78 ms 36932 KB Output is correct
14 Correct 78 ms 34512 KB Output is correct
15 Correct 252 ms 44308 KB Output is correct
16 Correct 271 ms 42644 KB Output is correct
17 Correct 263 ms 44228 KB Output is correct
18 Correct 262 ms 42160 KB Output is correct
19 Correct 103 ms 30052 KB Output is correct
20 Correct 263 ms 45176 KB Output is correct
21 Correct 243 ms 45324 KB Output is correct
22 Correct 282 ms 46524 KB Output is correct
23 Correct 248 ms 41780 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 22108 KB Output is correct
2 Correct 8 ms 22108 KB Output is correct
3 Incorrect 171 ms 33388 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 22108 KB Output is correct
2 Correct 8 ms 22108 KB Output is correct
3 Correct 8 ms 22108 KB Output is correct
4 Correct 8 ms 22108 KB Output is correct
5 Correct 9 ms 22048 KB Output is correct
6 Correct 8 ms 22108 KB Output is correct
7 Correct 8 ms 22340 KB Output is correct
8 Correct 8 ms 22108 KB Output is correct
9 Correct 8 ms 22364 KB Output is correct
10 Correct 91 ms 35212 KB Output is correct
11 Correct 86 ms 38560 KB Output is correct
12 Correct 84 ms 37116 KB Output is correct
13 Correct 106 ms 37744 KB Output is correct
14 Correct 78 ms 36932 KB Output is correct
15 Incorrect 7 ms 22108 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 22108 KB Output is correct
2 Correct 8 ms 22108 KB Output is correct
3 Correct 8 ms 22108 KB Output is correct
4 Correct 9 ms 22048 KB Output is correct
5 Correct 8 ms 22108 KB Output is correct
6 Correct 8 ms 22340 KB Output is correct
7 Correct 8 ms 22108 KB Output is correct
8 Correct 8 ms 22364 KB Output is correct
9 Correct 91 ms 35212 KB Output is correct
10 Correct 86 ms 38560 KB Output is correct
11 Correct 84 ms 37116 KB Output is correct
12 Correct 106 ms 37744 KB Output is correct
13 Correct 78 ms 36932 KB Output is correct
14 Correct 78 ms 34512 KB Output is correct
15 Correct 252 ms 44308 KB Output is correct
16 Correct 271 ms 42644 KB Output is correct
17 Correct 263 ms 44228 KB Output is correct
18 Correct 262 ms 42160 KB Output is correct
19 Incorrect 171 ms 33388 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 22108 KB Output is correct
2 Correct 8 ms 22108 KB Output is correct
3 Correct 8 ms 22108 KB Output is correct
4 Correct 8 ms 22108 KB Output is correct
5 Correct 9 ms 22048 KB Output is correct
6 Correct 8 ms 22108 KB Output is correct
7 Correct 8 ms 22340 KB Output is correct
8 Correct 8 ms 22108 KB Output is correct
9 Correct 8 ms 22364 KB Output is correct
10 Correct 91 ms 35212 KB Output is correct
11 Correct 86 ms 38560 KB Output is correct
12 Correct 84 ms 37116 KB Output is correct
13 Correct 106 ms 37744 KB Output is correct
14 Correct 78 ms 36932 KB Output is correct
15 Correct 78 ms 34512 KB Output is correct
16 Correct 252 ms 44308 KB Output is correct
17 Correct 271 ms 42644 KB Output is correct
18 Correct 263 ms 44228 KB Output is correct
19 Correct 262 ms 42160 KB Output is correct
20 Incorrect 171 ms 33388 KB Output isn't correct
21 Halted 0 ms 0 KB -