oj.uz

Submission #434544

# Submission time Handle Problem Language Result Execution time Memory
434544 2021-06-21T11:51:01 Z dqhungdl Swapping Cities (APIO20_swap) C++17
13 / 100
 232 ms 26392 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);
		swap(rootU,rootV);
	}
	P[v]=u;
	//cerr<<segs[u].first<<' '<<segs[u].second<<'\n';
	//cerr<<segs[v].first<<' '<<segs[v].second<<'\n';
	//cerr<<rootU<<' '<<rootV<<'\n';
	segs[u]=getNewSeg(segs[u],segs[v],rootU,rootV);
	//cerr<<segs[u].first<<' '<<segs[u].second<<"\n\n";
	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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 3 ms 4916 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 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 65 ms 14612 KB Output is correct
10 Correct 98 ms 16144 KB Output is correct
11 Correct 81 ms 16084 KB Output is correct
12 Correct 85 ms 16712 KB Output is correct
13 Correct 89 ms 16312 KB Output is correct
14 Correct 73 ms 16396 KB Output is correct
15 Correct 150 ms 22796 KB Output is correct
16 Correct 144 ms 22272 KB Output is correct
17 Correct 161 ms 23060 KB Output is correct
18 Correct 141 ms 20200 KB Output is correct
19 Correct 80 ms 12512 KB Output is correct
20 Correct 184 ms 25496 KB Output is correct
21 Correct 232 ms 25332 KB Output is correct
22 Correct 201 ms 26392 KB Output is correct
23 Correct 183 ms 24240 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 175 ms 18824 KB Output is correct
4 Correct 175 ms 19220 KB Output is correct
5 Correct 177 ms 19152 KB Output is correct
6 Correct 210 ms 19204 KB Output is correct
7 Correct 189 ms 19256 KB Output is correct
8 Correct 182 ms 18824 KB Output is correct
9 Correct 186 ms 19060 KB Output is correct
10 Correct 170 ms 18740 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 3 ms 4916 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 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Incorrect 4 ms 5068 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 3 ms 4916 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 65 ms 14612 KB Output is correct
11 Correct 98 ms 16144 KB Output is correct
12 Correct 81 ms 16084 KB Output is correct
13 Correct 85 ms 16712 KB Output is correct
14 Correct 89 ms 16312 KB Output is correct
15 Incorrect 4 ms 5068 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 3 ms 4916 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 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 65 ms 14612 KB Output is correct
10 Correct 98 ms 16144 KB Output is correct
11 Correct 81 ms 16084 KB Output is correct
12 Correct 85 ms 16712 KB Output is correct
13 Correct 89 ms 16312 KB Output is correct
14 Correct 73 ms 16396 KB Output is correct
15 Correct 150 ms 22796 KB Output is correct
16 Correct 144 ms 22272 KB Output is correct
17 Correct 161 ms 23060 KB Output is correct
18 Correct 141 ms 20200 KB Output is correct
19 Correct 175 ms 18824 KB Output is correct
20 Correct 175 ms 19220 KB Output is correct
21 Correct 177 ms 19152 KB Output is correct
22 Correct 210 ms 19204 KB Output is correct
23 Correct 189 ms 19256 KB Output is correct
24 Correct 182 ms 18824 KB Output is correct
25 Correct 186 ms 19060 KB Output is correct
26 Correct 170 ms 18740 KB Output is correct
27 Incorrect 4 ms 5068 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 3 ms 4916 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 65 ms 14612 KB Output is correct
11 Correct 98 ms 16144 KB Output is correct
12 Correct 81 ms 16084 KB Output is correct
13 Correct 85 ms 16712 KB Output is correct
14 Correct 89 ms 16312 KB Output is correct
15 Correct 73 ms 16396 KB Output is correct
16 Correct 150 ms 22796 KB Output is correct
17 Correct 144 ms 22272 KB Output is correct
18 Correct 161 ms 23060 KB Output is correct
19 Correct 141 ms 20200 KB Output is correct
20 Correct 175 ms 18824 KB Output is correct
21 Correct 175 ms 19220 KB Output is correct
22 Correct 177 ms 19152 KB Output is correct
23 Correct 210 ms 19204 KB Output is correct
24 Correct 189 ms 19256 KB Output is correct
25 Correct 182 ms 18824 KB Output is correct
26 Correct 186 ms 19060 KB Output is correct
27 Correct 170 ms 18740 KB Output is correct
28 Incorrect 4 ms 5068 KB Output isn't correct
29 Halted 0 ms 0 KB -