oj.uz

Submission #616097

# Submission time Handle Problem Language Result Execution time Memory
616097 2022-07-31T20:35:50 Z sofapuden Fountain Parks (IOI21_parks) C++17
0 / 100
 0 ms 212 KB 
#include "parks.h"
#include<bits/stdc++.h>

using namespace std;

vector<int> p;
vector<pair<int,int>> v;
set<pair<int,int>> ben;
map<pair<int,int>,int> M;

vector<int> U, V, A, B;

int u(int x){return p[x] == x ? x : p[x] = u(p[x]);}

void b(int x, int y){
	if(u(x) == u(y))return;
	if(v[x] > v[y])swap(x,y);
	if(v[x].first == v[y].first){
		if((v[x].second+v[x].first)%4 == 2){
			if(ben.count({v[x].second+1,v[x].first-1}))return;
			ben.insert({v[x].second+1,v[x].first-1});
			U.push_back(M[v[x]]);
			V.push_back(M[v[y]]);
			A.push_back(v[x].first-1);
			B.push_back(v[x].second+1);
			p[u(x)] = u(y);
		} else {
			if(ben.count({v[x].second+1,v[x].first+1}))return;
			ben.insert({v[x].second+1,v[x].first+1});
			U.push_back(M[v[x]]);
			V.push_back(M[v[y]]);
			A.push_back(v[x].first+1);
			B.push_back(v[x].second+1);
			p[u(x)] = u(y);
		}
	} else {
		if((v[x].second+v[x].first)%4 == 2){
			if(ben.count({v[x].second+1,v[x].first+1}))return;
			ben.insert({v[x].second+1,v[x].first+1});
			U.push_back(M[v[x]]);
			V.push_back(M[v[y]]);
			A.push_back(v[x].first+1);
			B.push_back(v[x].second+1);
			p[u(x)] = u(y);
		} else {
			if(ben.count({v[x].second-1,v[x].first+1}))return;
			ben.insert({v[x].second-1,v[x].first+1});
			U.push_back(M[v[x]]);
			V.push_back(M[v[y]]);
			A.push_back(v[x].first+1);
			B.push_back(v[x].second-1);
			p[u(x)] = u(y);
		}
	}
}

int construct_roads(vector<int> x, vector<int> y) {	
	int n = x.size();
	p.resize(n);
	iota(p.begin(),p.end(),0);
	for(int i = 0; i < n; ++i){v.emplace_back(x[i],y[i]);M[v.back()]=i;}
	map<pair<int,int>,int> S;
	sort(v.begin(),v.end());
	for(int i = 0; i < n; ++i){
		if(S[{v[i].first-2,v[i].second}])b(i,S[{v[i].first-2,v[i].second}]-1);
		if(S[{v[i].first,v[i].second-2}])b(i,S[{v[i].first,v[i].second-2}]-1);
		S[{v[i].first,v[i].second}] = i+1;
	}
	build(U,V,A,B);
	return 1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -