oj.uz

Submission #895065

# Submission time Handle Problem Language Result Execution time Memory
895065 2023-12-29T11:29:45 Z Muhammad_Aneeq Fountain Parks (IOI21_parks) C++17
5 / 100
 611 ms 46756 KB 
#include <vector>
#include <map>
#include <queue>
#include "parks.h"
using namespace std;
map<pair<int,int>,int>d,vis;
vector<pair<int,int>>z;
queue<pair<int,int>>Q;
int x1=0,y11=0;
void check(int x,int y)
{
	if (d.find({x,y})!=d.end()&&!vis[{x,y}])
	{
		Q.push({x,y});
		vis[{x,y}]=1;
		z.push_back({d[{x1,y11}],d[{x,y}]});
	}
}
void bfs(int x,int y)
{
	Q.push({x,y});
	vis[{x,y}]=1;
	while (Q.size())
	{
		x,y;
		tie(x,y)=Q.front();
		x1=x,y11=y;
		Q.pop();
		check(x,y-2);
		check(x,y+2);
		check(x-2,y);
		check(x+2,y);
	}
}
int construct_roads(vector<int> x, vector<int> y)
{
	int n=x.size();
	for (int i=0;i<n;i++)
		d[{x[i],y[i]}]=i;
	int reqx=1e9+10,reqy=1e9+10;
	for (int i=0;i<n;i++)
	{
		if (x[i]<reqx)
		{
			reqx=x[i];
			reqy=y[i];
		}
		else if (x[i]==reqx&&reqy<y[i])
			reqy=y[i];
	}
	bfs(reqx,reqy);
	for (int i=0;i<n;i++)
	{
		if (!vis[{x[i],y[i]}])
			return 0;
	}
	vis={};
	vector<int>u,v,a,b;
	//cout<<endl;
	for (auto i:z)
	{
		u.push_back(i.first);
		v.push_back(i.second);
		pair<int,int>r,q;
		r.first=x[i.first],r.second=y[i.first];
		q.first=x[i.second],q.second=y[i.second];
		if (r.first-q.first==0)
		{
			a.push_back(r.first-1);
			b.push_back((r.second+q.second)/2);
			if (vis[{a.back(),b.back()}])
			{
				a.pop_back();
				a.push_back(r.first+1);
				if (vis[{a.back(),b.back()}])
					return 0;
				vis[{a.back(),b.back()}]=1;
			}
			else
				vis[{a.back(),b.back()}]=1;
		}
		else
		{
			a.push_back((r.first+q.first)/2);
			b.push_back(r.second-1);
			if (vis[{a.back(),b.back()}])
			{
				b.pop_back();
				b.push_back(r.second+1);
				if (vis[{a.back(),b.back()}])
					return 0;
				vis[{a.back(),b.back()}]=1;
			}
			else
				vis[{a.back(),b.back()}]=1;
		}
	}
	build(u,v,a,b);
	return 1;
}

Compilation message

parks.cpp: In function 'void bfs(int, int)':
parks.cpp:25:3: warning: left operand of comma operator has no effect [-Wunused-value]
   25 |   x,y;
      |   ^
parks.cpp:25:6: warning: right operand of comma operator has no effect [-Wunused-value]
   25 |   x,y;
      |      ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 408 KB Output is correct
9 Correct 179 ms 22300 KB Output is correct
10 Correct 16 ms 2652 KB Output is correct
11 Correct 85 ms 12064 KB Output is correct
12 Correct 22 ms 3760 KB Output is correct
13 Correct 22 ms 5208 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 193 ms 22196 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 408 KB Output is correct
9 Correct 179 ms 22300 KB Output is correct
10 Correct 16 ms 2652 KB Output is correct
11 Correct 85 ms 12064 KB Output is correct
12 Correct 22 ms 3760 KB Output is correct
13 Correct 22 ms 5208 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 193 ms 22196 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 512 ms 44588 KB Output is correct
24 Incorrect 0 ms 348 KB Solution announced impossible, but it is possible.
25 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 408 KB Output is correct
9 Correct 179 ms 22300 KB Output is correct
10 Correct 16 ms 2652 KB Output is correct
11 Correct 85 ms 12064 KB Output is correct
12 Correct 22 ms 3760 KB Output is correct
13 Correct 22 ms 5208 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 193 ms 22196 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 512 ms 44588 KB Output is correct
24 Incorrect 0 ms 348 KB Solution announced impossible, but it is possible.
25 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 408 KB Output is correct
9 Correct 179 ms 22300 KB Output is correct
10 Correct 16 ms 2652 KB Output is correct
11 Correct 85 ms 12064 KB Output is correct
12 Correct 22 ms 3760 KB Output is correct
13 Correct 22 ms 5208 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 193 ms 22196 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 450 ms 46756 KB Output is correct
21 Correct 417 ms 45984 KB Output is correct
22 Correct 472 ms 45852 KB Output is correct
23 Correct 357 ms 38296 KB Output is correct
24 Correct 116 ms 17736 KB Output is correct
25 Correct 103 ms 17492 KB Output is correct
26 Correct 91 ms 17628 KB Output is correct
27 Correct 545 ms 44448 KB Output is correct
28 Correct 570 ms 44708 KB Output is correct
29 Correct 611 ms 44224 KB Output is correct
30 Incorrect 479 ms 31936 KB Solution announced impossible, but it is possible.
31 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 408 KB Output is correct
9 Correct 179 ms 22300 KB Output is correct
10 Correct 16 ms 2652 KB Output is correct
11 Correct 85 ms 12064 KB Output is correct
12 Correct 22 ms 3760 KB Output is correct
13 Correct 22 ms 5208 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 193 ms 22196 KB Output is correct
17 Correct 433 ms 45308 KB Output is correct
18 Correct 441 ms 45572 KB Output is correct
19 Correct 412 ms 45748 KB Output is correct
20 Correct 560 ms 42884 KB Output is correct
21 Correct 515 ms 38664 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Incorrect 46 ms 5384 KB Solution announced impossible, but it is possible.
24 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 408 KB Output is correct
9 Correct 179 ms 22300 KB Output is correct
10 Correct 16 ms 2652 KB Output is correct
11 Correct 85 ms 12064 KB Output is correct
12 Correct 22 ms 3760 KB Output is correct
13 Correct 22 ms 5208 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 193 ms 22196 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 512 ms 44588 KB Output is correct
24 Incorrect 0 ms 348 KB Solution announced impossible, but it is possible.
25 Halted 0 ms 0 KB -