oj.uz

Submission #894896

# Submission time Handle Problem Language Result Execution time Memory
894896 2023-12-29T07:36:06 Z MuhammadSaram Fountain Parks (IOI21_parks) C++17
5 / 100
 783 ms 59980 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()

void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);

const int M = 2e5;

set<int> nei[M];
bool vis[M];

void dfs(int u)
{
	vis[u]=true;
	for (int i:nei[u])
		if (!vis[i])
			dfs(i);
}

int construct_roads(vector<int> x, vector<int> y)
{
	int n=x.size();
	map<pair<int,int>,int> ind;
	for (int i=0;i<n;i++)
		ind[{x[i],y[i]}]=i;
	for (int i=0;i<n;i++)
		for (int j=-2;j<=2;j+=2)
			for (int k=-2;k<=2;k+=2)
			{
				if ((j==0)==(k==0))
					continue;
				if (ind.find({x[i]+j,y[i]+k})!=ind.end())
					nei[i].insert(ind[{x[i]+j,y[i]+k}]);
			}
	dfs(0);
	for (int i=0;i<n;i++)
		if (!vis[i])
			return 0;
	set<pair<int,int>> se;
	vector<int> u,v,a,b;
	for (int i=0;i<n;i++)
	{
		bool o=true;
		for (int j=-2;j<=2 and o;j+=2)
			for (int k=-2;k<=2 and o;k+=2)
			{
				if ((j==0)==(k==0))
					continue;
				if (ind.find({x[i]+j,y[i]+k})==ind.end())
					o=false;
			}
		if (o)
		{
			u.push_back(i),v.push_back(ind[{x[i],y[i]-2}]);
			a.push_back(x[i]-1),b.push_back(y[i]-1);
			se.insert({a.back(),b.back()});
			u.push_back(i),v.push_back(ind[{x[i]-2,y[i]}]);
			a.push_back(x[i]-1),b.push_back(y[i]+1);
			se.insert({a.back(),b.back()});
			u.push_back(i),v.push_back(ind[{x[i],y[i]+2}]);
			a.push_back(x[i]+1),b.push_back(y[i]+1);
			se.insert({a.back(),b.back()});
			u.push_back(i),v.push_back(ind[{x[i]+2,y[i]}]);
			a.push_back(x[i]+1),b.push_back(y[i]-1);
			se.insert({a.back(),b.back()});
			nei[i].erase(ind[{x[i],y[i]-2}]),nei[ind[{x[i],y[i]-2}]].erase(i);
			nei[i].erase(ind[{x[i]-2,y[i]}]),nei[ind[{x[i]-2,y[i]}]].erase(i);
			nei[i].erase(ind[{x[i],y[i]+2}]),nei[ind[{x[i],y[i]+2}]].erase(i);
			nei[i].erase(ind[{x[i]+2,y[i]}]),nei[ind[{x[i]+2,y[i]}]].erase(i);
		}
	}
	for (int i=0;i<n;i++)
		for (int j:nei[i])
		{
			if (x[i]==x[j])
			{
				int avg=(y[i]+y[j])/2;
				if (se.find({x[i]-1,avg})==se.end())
				{
					u.push_back(i),v.push_back(j);
					a.push_back(x[i]-1),b.push_back(avg);
					se.insert({a.back(),b.back()});
				}
				else
				{
					u.push_back(i),v.push_back(j);
					a.push_back(x[i]+1),b.push_back(avg);
					se.insert({a.back(),b.back()});
				}
			}
			else
			{
				int avg=(x[i]+x[j])/2;
				if (se.find({avg,y[i]-1})==se.end())
				{
					u.push_back(i),v.push_back(j);
					a.push_back(avg),b.push_back(y[i]-1);
					se.insert({a.back(),b.back()});
				}
				else
				{
					u.push_back(i),v.push_back(j);
					a.push_back(avg),b.push_back(y[i]+1);
					se.insert({a.back(),b.back()});
				}
			}
			nei[j].erase(i);
		}
	build(u,v,a,b);
	return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10072 KB Output is correct
2 Correct 2 ms 9864 KB Output is correct
3 Correct 2 ms 9872 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9868 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9816 KB Output is correct
9 Correct 218 ms 34232 KB Output is correct
10 Correct 13 ms 12380 KB Output is correct
11 Correct 83 ms 23112 KB Output is correct
12 Correct 19 ms 13708 KB Output is correct
13 Correct 39 ms 18260 KB Output is correct
14 Correct 3 ms 9820 KB Output is correct
15 Correct 4 ms 10076 KB Output is correct
16 Correct 230 ms 33484 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10072 KB Output is correct
2 Correct 2 ms 9864 KB Output is correct
3 Correct 2 ms 9872 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9868 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9816 KB Output is correct
9 Correct 218 ms 34232 KB Output is correct
10 Correct 13 ms 12380 KB Output is correct
11 Correct 83 ms 23112 KB Output is correct
12 Correct 19 ms 13708 KB Output is correct
13 Correct 39 ms 18260 KB Output is correct
14 Correct 3 ms 9820 KB Output is correct
15 Correct 4 ms 10076 KB Output is correct
16 Correct 230 ms 33484 KB Output is correct
17 Correct 2 ms 9820 KB Output is correct
18 Correct 2 ms 9820 KB Output is correct
19 Correct 2 ms 9816 KB Output is correct
20 Incorrect 2 ms 9656 KB Tree @(3, 5) appears more than once: for edges on positions 3 and 8
21 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10072 KB Output is correct
2 Correct 2 ms 9864 KB Output is correct
3 Correct 2 ms 9872 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9868 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9816 KB Output is correct
9 Correct 218 ms 34232 KB Output is correct
10 Correct 13 ms 12380 KB Output is correct
11 Correct 83 ms 23112 KB Output is correct
12 Correct 19 ms 13708 KB Output is correct
13 Correct 39 ms 18260 KB Output is correct
14 Correct 3 ms 9820 KB Output is correct
15 Correct 4 ms 10076 KB Output is correct
16 Correct 230 ms 33484 KB Output is correct
17 Correct 2 ms 9820 KB Output is correct
18 Correct 2 ms 9820 KB Output is correct
19 Correct 2 ms 9816 KB Output is correct
20 Incorrect 2 ms 9656 KB Tree @(3, 5) appears more than once: for edges on positions 3 and 8
21 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10072 KB Output is correct
2 Correct 2 ms 9864 KB Output is correct
3 Correct 2 ms 9872 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9868 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9816 KB Output is correct
9 Correct 218 ms 34232 KB Output is correct
10 Correct 13 ms 12380 KB Output is correct
11 Correct 83 ms 23112 KB Output is correct
12 Correct 19 ms 13708 KB Output is correct
13 Correct 39 ms 18260 KB Output is correct
14 Correct 3 ms 9820 KB Output is correct
15 Correct 4 ms 10076 KB Output is correct
16 Correct 230 ms 33484 KB Output is correct
17 Correct 2 ms 9820 KB Output is correct
18 Correct 3 ms 10068 KB Output is correct
19 Correct 3 ms 9872 KB Output is correct
20 Incorrect 783 ms 59980 KB Tree @(175213, 24791) appears more than once: for edges on positions 809 and 1243
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10072 KB Output is correct
2 Correct 2 ms 9864 KB Output is correct
3 Correct 2 ms 9872 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9868 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9816 KB Output is correct
9 Correct 218 ms 34232 KB Output is correct
10 Correct 13 ms 12380 KB Output is correct
11 Correct 83 ms 23112 KB Output is correct
12 Correct 19 ms 13708 KB Output is correct
13 Correct 39 ms 18260 KB Output is correct
14 Correct 3 ms 9820 KB Output is correct
15 Correct 4 ms 10076 KB Output is correct
16 Correct 230 ms 33484 KB Output is correct
17 Correct 674 ms 59136 KB Output is correct
18 Correct 659 ms 59384 KB Output is correct
19 Incorrect 765 ms 59928 KB Tree @(29861, 20145) appears more than once: for edges on positions 1096 and 4556
20 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10072 KB Output is correct
2 Correct 2 ms 9864 KB Output is correct
3 Correct 2 ms 9872 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9868 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9816 KB Output is correct
9 Correct 218 ms 34232 KB Output is correct
10 Correct 13 ms 12380 KB Output is correct
11 Correct 83 ms 23112 KB Output is correct
12 Correct 19 ms 13708 KB Output is correct
13 Correct 39 ms 18260 KB Output is correct
14 Correct 3 ms 9820 KB Output is correct
15 Correct 4 ms 10076 KB Output is correct
16 Correct 230 ms 33484 KB Output is correct
17 Correct 2 ms 9820 KB Output is correct
18 Correct 2 ms 9820 KB Output is correct
19 Correct 2 ms 9816 KB Output is correct
20 Incorrect 2 ms 9656 KB Tree @(3, 5) appears more than once: for edges on positions 3 and 8
21 Halted 0 ms 0 KB -