oj.uz

Submission #754268

# Submission time Handle Problem Language Result Execution time Memory
754268 2023-06-07T11:35:54 Z tolbi Fountain Parks (IOI21_parks) C++17
5 / 100
 1062 ms 53024 KB 
#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& in, pair<X,Y> &pr) {return in>>pr.first>>pr.second;}
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr) {return os<<pr.first<<" "<<pr.second;}
template<typename X> istream& operator>>(istream& in, vector<X> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X> ostream& operator<<(ostream& os, vector<X> arr) {for(auto &it : arr) os<<it<<" "; return os;}
template<typename X, size_t Y> istream& operator>>(istream& in, array<X,Y> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> arr) {for(auto &it : arr) os<<it<<" "; return os;}
template<typename T> vector<int32_t> normalize(vector<T> &arr){vector<int> rv;rv.resize(arr.size());for (int i = 0; i < rv.size(); ++i){rv[i]=arr[i];}return rv;}
#define endl '\n'
#define vint(x) vector<int> x
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(),x.end())
#define sortrarr(x) sort(x.rbegin(),x.rend())
#define det(x) cout<<"NO\0YES"+x*3<<endl;
#define INF LONG_MAX
#define rev(x) reverse(x.begin(),x.end());
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define tol(bi) (1LL<<((int)(bi)))
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "parks.h"
struct DSU{
	vector<int> par;
	DSU(int n){
		par.resize(n);
		iota(par.begin(), par.end(), 0ll);
	}
	int find(int node){
		if (par[node]==node) return node;
		return par[node]=find(par[node]);
	}
	void merge(int a, int b){
		a=find(a);
		b=find(b);
		if (ayahya()%2) swap(a,b);
		par[a]=b;
	}
};
int construct_roads(vector<int> x, vector<int> y) {
	map<pair<int,int>,int> mp;
	int n = x.size();
	for (int i = 0; i < n; ++i)
	{
		mp[{x[i],y[i]}]=i;
	}
	map<pair<int,int>,int> dikey;
	map<pair<int,int>,int> yatay;
	vector<bool> yat;
	vector<int> u;
	vector<int> v;
	vector<int> a;
	vector<int> b;
	DSU dsu(n);
	for (int i = 0; i < n; i++){
		int xv = x[i];
		int yv = y[i];
		if (mp.count({xv+2,yv})){
			if (dsu.find(i)!=dsu.find(mp[{xv+2,yv}])){
				dsu.merge(i,mp[{xv+2,yv}]);
				yatay[{xv,yv}]=u.size();
				u.push_back(i);
				v.push_back(mp[{xv+2,yv}]);
				yat.push_back(true);
				a.push_back(-23);
				b.push_back(-23);
			}
		}
		if (mp.count({xv,yv+2})){
			if (dsu.find(i)!=dsu.find(mp[{xv,yv+2}])){
				dsu.merge(i,mp[{xv,yv+2}]);
				dikey[{xv,yv}]=u.size();
				u.push_back(i);
				v.push_back(mp[{xv,yv+2}]);
				yat.push_back(false);
				a.push_back(-23);
				b.push_back(-23);
			}
		}
	}
	if (u.size()!=n-1) return 0;
	map<pair<int,int>,bool> kap;
	int mini = *min_element(x.begin(), x.end());
	int minj = *min_element(y.begin(), y.end());
	int mani = *max_element(x.begin(), x.end());
	int manj = *max_element(y.begin(), y.end());
	vector<int> sir;
	vector<int> viss(u.size(),false);
	for (int i = 0; i < u.size(); i++){
		if (x[u[i]]==mini && !yat[i]){
			a[i]=x[u[i]]-1;
			b[i]=y[u[i]]+1;
			viss[i]=true;
			continue;
		}
		if (x[u[i]]==mani && !yat[i]){
			a[i]=x[u[i]]+1;
			b[i]=y[u[i]]+1;
			viss[i]=true;
			continue;
		}
		if (y[u[i]]==minj & yat[i]){
			a[i]=x[u[i]]+1;
			b[i]=y[u[i]]-1;
			viss[i]=true;
			continue;
		}
		if (y[u[i]]==manj && yat[i]){
			a[i]=x[u[i]]+1;
			b[i]=y[u[i]]+1;
			viss[i]=true;
			continue;
		}
	}
	for (int i = 0; i < u.size(); ++i)
	{
		if (viss[i]) continue;
		int xv = x[u[i]];
		int yv = y[u[i]];
		if (yatay.count({xv,yv}) && dikey.count({xv,yv}) && yatay.count({xv-2,yv}) && dikey.count({xv,yv-2})){
			sir.push_back(i);
			viss[i]=true;
		}
	}
	for (int i = 0; i < u.size(); ++i){
		if (!yat[i]) continue;
		if (viss[i]) continue;
		sir.push_back(i);
		viss[i]=true;
	}
	for (int i = 0; i < u.size(); ++i)
	{
		if (viss[i]) continue;
		sir.push_back(i);
	}
	for (int i = 0; i < sir.size(); i++){
		int ed = sir[i];
		queue<int> q;
		q.push(i);
		while (q.size()){
			int ed = q.front();
			q.pop();
			if (a[ed]!=-23) break;
			if (yat[ed]){
				if (!kap[{x[u[ed]]+1,y[u[ed]]+1}]){
					kap[{x[u[ed]]+1,y[u[ed]]+1}]=true;
					a[ed]=x[u[ed]]+1;
					b[ed]=y[u[ed]]+1;
				}
				else {
					if (kap[{x[u[ed]]+1,y[u[ed]]-1}]) return 0;
					kap[{x[u[ed]]+1,y[u[ed]]-1}]=true;
					a[ed]=x[u[ed]]+1;
					b[ed]=y[u[ed]]-1;
				}
			}
			else {
				if (!kap[{x[u[ed]]+1,y[u[ed]]+1}]){
					kap[{x[u[ed]]+1,y[u[ed]]+1}]=true;
					a[ed]=x[u[ed]]+1;
					b[ed]=y[u[ed]]+1;
				}
				else {
					if (kap[{x[u[ed]]-1,y[u[ed]]+1}]) return 0;
					kap[{x[u[ed]]-1,y[u[ed]]+1}]=true;
					a[ed]=x[u[ed]]-1;
					b[ed]=y[u[ed]]+1;
				}
			}
			pair<int,int> pr;
			pr={a[ed]-1,b[ed]-1};
			if (yatay.count(pr) && yatay[pr]!=ed && a[yatay[pr]]==-23){
				ed=yatay[pr];
				continue;
			}
			pr={a[ed]-1,b[ed]+1};
			if (yatay.count(pr) && yatay[pr]!=ed && a[yatay[pr]]==-23){
				ed=yatay[pr];
				continue;
			}			
			pr={a[ed]-1,b[ed]-1};
			if (dikey.count(pr) && dikey[pr]!=ed && a[dikey[pr]]==-23){
				ed=dikey[pr];
				continue;
			}			
			pr={a[ed]+1,b[ed]-1};
			if (dikey.count(pr) && dikey[pr]!=ed && a[dikey[pr]]==-23){
				ed=dikey[pr];
				continue;
			}
		}
	}
	build(u,v,a,b);
	return 1;
}

Compilation message

parks.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:95:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |  if (u.size()!=n-1) return 0;
      |      ~~~~~~~~^~~~~
parks.cpp:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |  for (int i = 0; i < u.size(); i++){
      |                  ~~^~~~~~~~~~
parks.cpp:116:14: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  116 |   if (y[u[i]]==minj & yat[i]){
parks.cpp:129:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |  for (int i = 0; i < u.size(); ++i)
      |                  ~~^~~~~~~~~~
parks.cpp:139:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |  for (int i = 0; i < u.size(); ++i){
      |                  ~~^~~~~~~~~~
parks.cpp:145:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |  for (int i = 0; i < u.size(); ++i)
      |                  ~~^~~~~~~~~~
parks.cpp:150:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |  for (int i = 0; i < sir.size(); i++){
      |                  ~~^~~~~~~~~~~~
parks.cpp:151:7: warning: unused variable 'ed' [-Wunused-variable]
  151 |   int ed = sir[i];
      |       ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 240 ms 20128 KB Output is correct
10 Correct 13 ms 2516 KB Output is correct
11 Correct 80 ms 11044 KB Output is correct
12 Correct 20 ms 3616 KB Output is correct
13 Correct 50 ms 7648 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 257 ms 20052 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 240 ms 20128 KB Output is correct
10 Correct 13 ms 2516 KB Output is correct
11 Correct 80 ms 11044 KB Output is correct
12 Correct 20 ms 3616 KB Output is correct
13 Correct 50 ms 7648 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 257 ms 20052 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Incorrect 1 ms 344 KB Tree (a[3], b[3]) = (-23, -23) is not adjacent to edge between u[3]=3 @(2, 4) and v[3]=6 @(4, 4)
21 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 240 ms 20128 KB Output is correct
10 Correct 13 ms 2516 KB Output is correct
11 Correct 80 ms 11044 KB Output is correct
12 Correct 20 ms 3616 KB Output is correct
13 Correct 50 ms 7648 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 257 ms 20052 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Incorrect 1 ms 344 KB Tree (a[3], b[3]) = (-23, -23) is not adjacent to edge between u[3]=3 @(2, 4) and v[3]=6 @(4, 4)
21 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 240 ms 20128 KB Output is correct
10 Correct 13 ms 2516 KB Output is correct
11 Correct 80 ms 11044 KB Output is correct
12 Correct 20 ms 3616 KB Output is correct
13 Correct 50 ms 7648 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 257 ms 20052 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 308 KB Output is correct
20 Incorrect 1062 ms 53024 KB Tree (a[199996], b[199996]) = (-23, -23) is not adjacent to edge between u[199996]=199997 @(147678, 52324) and v[199996]=47377 @(147680, 52324)
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 240 ms 20128 KB Output is correct
10 Correct 13 ms 2516 KB Output is correct
11 Correct 80 ms 11044 KB Output is correct
12 Correct 20 ms 3616 KB Output is correct
13 Correct 50 ms 7648 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 257 ms 20052 KB Output is correct
17 Correct 671 ms 39744 KB Output is correct
18 Incorrect 778 ms 43296 KB Tree (a[100001], b[100001]) = (-23, -23) is not adjacent to edge between u[100001]=100001 @(50002, 92930) and v[100001]=198938 @(50002, 92932)
19 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 240 ms 20128 KB Output is correct
10 Correct 13 ms 2516 KB Output is correct
11 Correct 80 ms 11044 KB Output is correct
12 Correct 20 ms 3616 KB Output is correct
13 Correct 50 ms 7648 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 257 ms 20052 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Incorrect 1 ms 344 KB Tree (a[3], b[3]) = (-23, -23) is not adjacent to edge between u[3]=3 @(2, 4) and v[3]=6 @(4, 4)
21 Halted 0 ms 0 KB -