Submission #954361

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
954361	2024-03-27T16:47:54 Z	amirhoseinfar1385	Swapping Cities (APIO20_swap)	C++17	0 / 100	2000 ms	25224 KB

swap

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-