oj.uz

Submission #1044591

# Submission time Handle Problem Language Result Execution time Memory
1044591 2024-08-05T11:25:43 Z Unforgettablepl Fountain Parks (IOI21_parks) C++17
5 / 100
 538 ms 54692 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;

int construct_roads(vector<int> x,vector<int> y){
	int n = x.size();
	map<pair<int,int>,int> lookup;
	set<pair<int,int>> edges;
	for(int i=0;i<n;i++)lookup[{x[i],y[i]}]=i;
	vector<int> u,v,a,b;
	vector<vector<int>> adj(n);
	for(int i=0;i<n;i++){
		bool works = false;
		if(lookup.count({x[i]+2,y[i]})){
			works=true;
			if(edges.count({i,lookup[{x[i]+2,y[i]}]}))continue;
			edges.emplace(lookup[{x[i]+2,y[i]}],i);
			u.emplace_back(i);
			v.emplace_back(lookup[{x[i]+2,y[i]}]);
			adj[i].emplace_back(lookup[{x[i]+2,y[i]}]);
			adj[lookup[{x[i]+2,y[i]}]].emplace_back(i);
			a.emplace_back(x[i]+1);
			b.emplace_back(y[i]-1);
		}
		if(lookup.count({x[i]-2,y[i]})){
			works = true;
			if(edges.count({i,lookup[{x[i]-2,y[i]}]}))continue;
			edges.emplace(lookup[{x[i]-2,y[i]}],i);
			u.emplace_back(i);
			v.emplace_back(lookup[{x[i]-2,y[i]}]);
			adj[i].emplace_back(lookup[{x[i]-2,y[i]}]);
			adj[lookup[{x[i]-2,y[i]}]].emplace_back(i);
			a.emplace_back(x[i]-1);
			b.emplace_back(y[i]-1);
		}
		if(x[i]==4 and works)continue;
		if(lookup.count({x[i],y[i]+2})){
			if(edges.count({i,lookup[{x[i],y[i]+2}]}))continue;
			edges.emplace(lookup[{x[i],y[i]+2}],i);
			u.emplace_back(i);
			v.emplace_back(lookup[{x[i],y[i]+2}]);
			adj[i].emplace_back(lookup[{x[i],y[i]+2}]);
			adj[lookup[{x[i],y[i]+2}]].emplace_back(i);
			if(x[i]==2)a.emplace_back(x[i]-1);
			else a.emplace_back(x[i]+1);
			b.emplace_back(y[i]+1);
		}
		if(lookup.count({x[i],y[i]-2})){
			if(edges.count({i,lookup[{x[i],y[i]-2}]}))continue;
			edges.emplace(lookup[{x[i],y[i]-2}],i);
			u.emplace_back(i);
			v.emplace_back(lookup[{x[i],y[i]-2}]);
			adj[i].emplace_back(lookup[{x[i],y[i]-2}]);
			adj[lookup[{x[i],y[i]-2}]].emplace_back(i);
			if(x[i]==2)a.emplace_back(x[i]-1);
			else a.emplace_back(x[i]+1);
			b.emplace_back(y[i]-1);
		}
	}
	vector<bool> visited(n);
	int vis = 0;
	function<void(int)> dfs = [&](int x){
		if(visited[x])return;
		visited[x]=true;
		vis++;
		for(int&i:adj[x])dfs(i);
	};
	dfs(0);
	if(vis!=n)return 0;
	build(u,v,a,b);
	return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 348 KB Output is correct
9 Correct 201 ms 28676 KB Output is correct
10 Correct 11 ms 3180 KB Output is correct
11 Correct 75 ms 15816 KB Output is correct
12 Correct 17 ms 4700 KB Output is correct
13 Correct 52 ms 10952 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 198 ms 26380 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 348 KB Output is correct
9 Correct 201 ms 28676 KB Output is correct
10 Correct 11 ms 3180 KB Output is correct
11 Correct 75 ms 15816 KB Output is correct
12 Correct 17 ms 4700 KB Output is correct
13 Correct 52 ms 10952 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 198 ms 26380 KB Output is correct
17 Incorrect 0 ms 348 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 348 KB Output is correct
9 Correct 201 ms 28676 KB Output is correct
10 Correct 11 ms 3180 KB Output is correct
11 Correct 75 ms 15816 KB Output is correct
12 Correct 17 ms 4700 KB Output is correct
13 Correct 52 ms 10952 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 198 ms 26380 KB Output is correct
17 Incorrect 0 ms 348 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 348 KB Output is correct
9 Correct 201 ms 28676 KB Output is correct
10 Correct 11 ms 3180 KB Output is correct
11 Correct 75 ms 15816 KB Output is correct
12 Correct 17 ms 4700 KB Output is correct
13 Correct 52 ms 10952 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 198 ms 26380 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 437 ms 37912 KB Solution announced impossible, but it is possible.
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 348 KB Output is correct
9 Correct 201 ms 28676 KB Output is correct
10 Correct 11 ms 3180 KB Output is correct
11 Correct 75 ms 15816 KB Output is correct
12 Correct 17 ms 4700 KB Output is correct
13 Correct 52 ms 10952 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 198 ms 26380 KB Output is correct
17 Correct 484 ms 54692 KB Output is correct
18 Incorrect 538 ms 53192 KB Tree @(50003, 50001) appears more than once: for edges on positions 127923 and 152181
19 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 348 KB Output is correct
9 Correct 201 ms 28676 KB Output is correct
10 Correct 11 ms 3180 KB Output is correct
11 Correct 75 ms 15816 KB Output is correct
12 Correct 17 ms 4700 KB Output is correct
13 Correct 52 ms 10952 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 198 ms 26380 KB Output is correct
17 Incorrect 0 ms 348 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -