Submission #954317

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
954317	2024-03-27T15:40:31 Z	amirhoseinfar1385	Swapping Cities (APIO20_swap)	C++17	0 / 100	2000 ms	16844 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;
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

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

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

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

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	4696 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 23.0

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

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	4696 KB	Output isn't correct
2	Halted	0 ms	0 KB	-