oj.uz

Submission #754271

# Submission time Handle Problem Language Result Execution time Memory
754271 2023-06-07T11:37:59 Z tolbi Fountain Parks (IOI21_parks) C++17
5 / 100
 1012 ms 52920 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) continue;
			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){
				q.push(yatay[pr]);
			}
			pr={a[ed]-1,b[ed]+1};
			if (yatay.count(pr) && yatay[pr]!=ed && a[yatay[pr]]==-23){
				q.push(yatay[pr]);
			}			
			pr={a[ed]-1,b[ed]-1};
			if (dikey.count(pr) && dikey[pr]!=ed && a[dikey[pr]]==-23){
				q.push(dikey[pr]);
			}			
			pr={a[ed]+1,b[ed]-1};
			if (dikey.count(pr) && dikey[pr]!=ed && a[dikey[pr]]==-23){
				q.push(dikey[pr]);
			}
		}
	}
	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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 260 ms 19888 KB Output is correct
10 Correct 14 ms 2388 KB Output is correct
11 Correct 82 ms 10800 KB Output is correct
12 Correct 22 ms 3540 KB Output is correct
13 Correct 53 ms 7352 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 262 ms 19832 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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 260 ms 19888 KB Output is correct
10 Correct 14 ms 2388 KB Output is correct
11 Correct 82 ms 10800 KB Output is correct
12 Correct 22 ms 3540 KB Output is correct
13 Correct 53 ms 7352 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 262 ms 19832 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Incorrect 0 ms 212 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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 260 ms 19888 KB Output is correct
10 Correct 14 ms 2388 KB Output is correct
11 Correct 82 ms 10800 KB Output is correct
12 Correct 22 ms 3540 KB Output is correct
13 Correct 53 ms 7352 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 262 ms 19832 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Incorrect 0 ms 212 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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 260 ms 19888 KB Output is correct
10 Correct 14 ms 2388 KB Output is correct
11 Correct 82 ms 10800 KB Output is correct
12 Correct 22 ms 3540 KB Output is correct
13 Correct 53 ms 7352 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 262 ms 19832 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1004 ms 52884 KB Output is correct
21 Correct 1012 ms 52808 KB Output is correct
22 Correct 987 ms 52920 KB Output is correct
23 Incorrect 569 ms 34360 KB Tree (a[40000], b[40000]) = (-23, -23) is not adjacent to edge between u[40000]=40002 @(60000, 19166) and v[40000]=78327 @(60000, 19168)
24 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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 260 ms 19888 KB Output is correct
10 Correct 14 ms 2388 KB Output is correct
11 Correct 82 ms 10800 KB Output is correct
12 Correct 22 ms 3540 KB Output is correct
13 Correct 53 ms 7352 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 262 ms 19832 KB Output is correct
17 Correct 670 ms 39420 KB Output is correct
18 Incorrect 729 ms 43064 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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 260 ms 19888 KB Output is correct
10 Correct 14 ms 2388 KB Output is correct
11 Correct 82 ms 10800 KB Output is correct
12 Correct 22 ms 3540 KB Output is correct
13 Correct 53 ms 7352 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 262 ms 19832 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Incorrect 0 ms 212 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 -