oj.uz

Submission #551097

# Submission time Handle Problem Language Result Execution time Memory
551097 2022-04-19T21:00:41 Z 1ne Fountain Parks (IOI21_parks) C++17
5 / 100
 930 ms 116336 KB 
#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
struct edges{
	int x,y,x1,y1;
};
int construct_roads(std::vector<int> x, std::vector<int> y) {
	 map<pair<int,int>,bool>mp,got,have;
	 map<pair<int,int>,int>index;
	 int n = (int)x.size();
	 for (int i = 0;i<n;++i){
		 mp[{x[i],y[i]}] = true;
		 got[{x[i],y[i]}] = false;
		 index[{x[i],y[i]}] = i;
	 }
	 vector<edges>ans;
	 vector<int>dx = {2,0,-2,0};
	 vector<int>dy = {0,2,0,-2};
	 function<void(int,int)> dfs = [&](int u,int v){
		 got[{u,v}] = true;
		 for (int i = 0;i<4;++i){
			 int xx = u + dx[i];
			 int yy = v + dy[i];
			 if (mp[{xx,yy}] && !got[{xx,yy}]){
				 ans.push_back({u,v,xx,yy});
				 dfs(xx,yy);
			 }
		 }
	 };
	 bool ok = true;
	 dfs(x[0],y[0]);
	 for (int i = 0;i<n;++i){
		 if (!got[{x[i],y[i]}]){
			 ok=false;
			 break;
		 }
	 }
	 if (!ok){
		 return 0;
	 }
	 sort(ans.begin(),ans.end(),[&](auto xx,auto yy){
		 return xx.x<yy.x;
	 });
	 vector<int>u,v,a,b;
	 for (auto z:ans){
		 int xx = max(z.x,z.x1);
		 int yy = max(z.y,z.y1);
		 u.push_back(index[{z.x,z.y}]);
		 v.push_back(index[{z.x1,z.y1}]);
		 if (z.x == z.x1){
			if (!have[{xx - 1,yy - 1}]){
				have[{xx - 1,yy - 1}] = true;
				a.push_back(xx - 1 );
				b.push_back(yy- 1);
			}
			else{
				a.push_back(xx + 1);
				b.push_back(yy - 1);
				have[{xx+1,yy - 1}] = true;
			}
		 }
		 else {
			 if (!have[{xx - 1,yy + 1}]){
				have[{xx - 1,yy + 1}] = true;
				a.push_back(xx-1);
				b.push_back(yy+ 1);
			}
			else{
				a.push_back(xx - 1);
				b.push_back(yy - 1);
				have[{xx - 1,yy - 1}] = true;
			}
		 }
	 }
	 build(u,v,a,b);
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 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 0 ms 212 KB Output is correct
9 Correct 400 ms 57296 KB Output is correct
10 Correct 26 ms 6096 KB Output is correct
11 Correct 158 ms 31552 KB Output is correct
12 Correct 37 ms 9032 KB Output is correct
13 Correct 74 ms 17248 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 387 ms 52188 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 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 0 ms 212 KB Output is correct
9 Correct 400 ms 57296 KB Output is correct
10 Correct 26 ms 6096 KB Output is correct
11 Correct 158 ms 31552 KB Output is correct
12 Correct 37 ms 9032 KB Output is correct
13 Correct 74 ms 17248 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 387 ms 52188 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Incorrect 930 ms 103704 KB Tree @(3, 60541) appears more than once: for edges on positions 84975 and 100041
24 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 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 0 ms 212 KB Output is correct
9 Correct 400 ms 57296 KB Output is correct
10 Correct 26 ms 6096 KB Output is correct
11 Correct 158 ms 31552 KB Output is correct
12 Correct 37 ms 9032 KB Output is correct
13 Correct 74 ms 17248 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 387 ms 52188 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Incorrect 930 ms 103704 KB Tree @(3, 60541) appears more than once: for edges on positions 84975 and 100041
24 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 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 0 ms 212 KB Output is correct
9 Correct 400 ms 57296 KB Output is correct
10 Correct 26 ms 6096 KB Output is correct
11 Correct 158 ms 31552 KB Output is correct
12 Correct 37 ms 9032 KB Output is correct
13 Correct 74 ms 17248 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 387 ms 52188 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 866 ms 103672 KB Output is correct
21 Incorrect 877 ms 98996 KB Tree @(9, 13) appears more than once: for edges on positions 8 and 11
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 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 0 ms 212 KB Output is correct
9 Correct 400 ms 57296 KB Output is correct
10 Correct 26 ms 6096 KB Output is correct
11 Correct 158 ms 31552 KB Output is correct
12 Correct 37 ms 9032 KB Output is correct
13 Correct 74 ms 17248 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 387 ms 52188 KB Output is correct
17 Correct 912 ms 116336 KB Output is correct
18 Correct 894 ms 106440 KB Output is correct
19 Incorrect 864 ms 104024 KB Tree @(50007, 99997) appears more than once: for edges on positions 100003 and 100004
20 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 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 0 ms 212 KB Output is correct
9 Correct 400 ms 57296 KB Output is correct
10 Correct 26 ms 6096 KB Output is correct
11 Correct 158 ms 31552 KB Output is correct
12 Correct 37 ms 9032 KB Output is correct
13 Correct 74 ms 17248 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 387 ms 52188 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Incorrect 930 ms 103704 KB Tree @(3, 60541) appears more than once: for edges on positions 84975 and 100041
24 Halted 0 ms 0 KB -