oj.uz

Submission #434524

# Submission time Handle Problem Language Result Execution time Memory
434524 2021-06-21T11:38:57 Z dqhungdl Swapping Cities (APIO20_swap) C++17
7 / 100
 255 ms 19196 KB 
#include "swap.h"

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
typedef pair<int,ii> iii;
const int MAX=1e5+5;
int P[MAX];
bool isLine[MAX];
ii segs[MAX];
vector<int> S[MAX];
vector<iii> edges;
vector<ii> history[MAX];

int find(int u) {
	if(P[u]==u)
		return u;
	return P[u]=find(P[u]);
}

ii getNewSeg(ii s1,ii s2,int u,int v) {
	if(s1.first==u) {
		if(s2.first==v)
			return {s1.second,s2.second};
		if(s2.second==v)
			return {s1.second,s2.first};
	} else if(s1.second==u) {
		if(s2.first==v)
			return {s1.first,s2.second};
		if(s2.second==v)
			return {s1.first,s2.first};
	}
	return {-1,-1};
}

void merge(int u,int v,int w,int rootU,int rootV) {
	if(S[u].size()<S[v].size())
		swap(u,v);
	P[v]=u;
	segs[u]=getNewSeg(segs[u],segs[v],rootU,rootV);
	bool newIsLine=(segs[u].first!=-1);
	if(isLine[u]!=newIsLine) {
		isLine[u]=false;
		for(int tmp:S[u])
			history[tmp].push_back({w,u});
	}
	if(isLine[v]!=newIsLine) {
		isLine[v]=false;
		for(int tmp:S[v])
			history[tmp].push_back({w,u});
	}
	while(S[v].size()>0) {
		int tmp=S[v].back();
		S[v].pop_back();
		S[u].push_back(tmp);
	}
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	for(int i=0;i<M;i++)
		edges.push_back({W[i],{U[i],V[i]}});
	sort(edges.begin(),edges.end());
	for(int i=0;i<N;i++) {
		P[i]=i;
		isLine[i]=true;
		segs[i]={i,i};
		S[i].push_back(i);
	}
	for(iii edge:edges) {
		int u=find(edge.second.first),v=find(edge.second.second),w=edge.first;
		if(u!=v)
			merge(u,v,w,edge.second.first,edge.second.second);
		else if(isLine[u]) {
			isLine[u]=false;
			segs[u]={-1,-1};
			for(int tmp:S[u])
				history[tmp].push_back({w,u});
		}
	}
	//for(ii tmp:history[0])
	//	cerr<<tmp.first<<' '<<tmp.second<<'\n';
}

int getMinimumFuelCapacity(int X, int Y) {
	vector<ii> hisX=history[X],hisY=history[Y];
	int rs=-1;
	while(hisX.size()>0&&hisY.size()>0&&hisX.back().second==hisY.back().second) {
		rs=max(hisX.back().first,hisY.back().first);
		hisX.pop_back(),hisY.pop_back();
	}
	return rs;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4988 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5064 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Incorrect 4 ms 5068 KB Output isn't correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4988 KB Output is correct
3 Correct 227 ms 18752 KB Output is correct
4 Correct 224 ms 19196 KB Output is correct
5 Correct 255 ms 19188 KB Output is correct
6 Correct 197 ms 19188 KB Output is correct
7 Correct 186 ms 19192 KB Output is correct
8 Correct 203 ms 18824 KB Output is correct
9 Correct 192 ms 19136 KB Output is correct
10 Correct 201 ms 18736 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4988 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5064 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Incorrect 4 ms 5068 KB Output isn't correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4988 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5064 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Incorrect 4 ms 5068 KB Output isn't correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4988 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5064 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Incorrect 4 ms 5068 KB Output isn't correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4988 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5064 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Incorrect 4 ms 5068 KB Output isn't correct