oj.uz

Submission #1052915

# Submission time Handle Problem Language Result Execution time Memory
1052915 2024-08-11T05:54:38 Z ReLice Fountain Parks (IOI21_parks) C++17
55 / 100
 461 ms 96124 KB 
#include "parks.h"
#include <bits/stdc++.h>
#define pb push_back
#define ll int
#define ins insert
#define sz size()
#define vll vector<ll>
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
using namespace std;
const int N=2e5+5;
const int inf=1e9;
map<pair<ll,ll>, ll> f;
vll xx, yy;

ll xd[4] = {-2, 2, 0, 0}, yd[4] = {0, 0, -2, 2};
ll bx[2][4] = {{-1, 1,  1, -1}, {-1,  1, -1,  1}};
ll by[2][4] = {{-1, 1, -1,  1}, { 1, -1, -1,  1}};

set<pair<ll,ll>> vis;
vll v,u,a,b;
ll n,c;
bool ok(ll x,ll y){
	bool free = (vis.find({x, y}) == vis.end());
	if(x % 2) return free;
	return free && f[{x,y}];
}
void dfs(ll x, ll y){
	vis.ins({x, y});
	c++;
	for(ll i=3;i>=0;i--){
		ll nx = x + xd[i], ny = y + yd[i];
		
		ll p = (x + y) / 2 % 2;
		ll aa = x + bx[p][i], bb = y + by[p][i];
		
		if(!ok(nx, ny) || !ok(aa, bb)) continue;
		
		v.pb(f[{x,y}]-1);
		u.pb(f[{nx,ny}]-1);
		a.pb(aa);
		b.pb(bb);
		
		vis.ins({aa, bb});
		
		dfs(nx, ny);
	}
}
int construct_roads(vector<int> X, vector<int> Y) {
	n=X.size();
	vector<pair<ll,ll>> V;
	
	for(int i=0;i<(int)X.size();i++){
		f[{X[i], Y[i]}] = i + 1;
		V.pb({X[i],Y[i]});
	}
	
	sort(all(V));
	
	xx.pb(0);
	yy.pb(0);
	for(auto i : X) xx.pb(i);
	for(auto i : Y) yy.pb(i);
	
	dfs(V[0].fr, V[0].sc);
	
	if((ll)u.size() != n - 1) 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 184 ms 47844 KB Output is correct
10 Correct 13 ms 5128 KB Output is correct
11 Correct 88 ms 25976 KB Output is correct
12 Correct 19 ms 7452 KB Output is correct
13 Correct 51 ms 15052 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 178 ms 47876 KB Output is correct

Subtask #2
10.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 184 ms 47844 KB Output is correct
10 Correct 13 ms 5128 KB Output is correct
11 Correct 88 ms 25976 KB Output is correct
12 Correct 19 ms 7452 KB Output is correct
13 Correct 51 ms 15052 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 178 ms 47876 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 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 380 ms 72156 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 860 KB Output is correct
26 Correct 2 ms 860 KB Output is correct
27 Correct 2 ms 860 KB Output is correct
28 Correct 119 ms 29104 KB Output is correct
29 Correct 214 ms 43404 KB Output is correct
30 Correct 278 ms 58096 KB Output is correct
31 Correct 388 ms 72160 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 344 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 1 ms 860 KB Output is correct
44 Correct 1 ms 904 KB Output is correct
45 Correct 161 ms 41816 KB Output is correct
46 Correct 272 ms 60748 KB Output is correct
47 Correct 263 ms 60748 KB Output is correct

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 184 ms 47844 KB Output is correct
10 Correct 13 ms 5128 KB Output is correct
11 Correct 88 ms 25976 KB Output is correct
12 Correct 19 ms 7452 KB Output is correct
13 Correct 51 ms 15052 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 178 ms 47876 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 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 380 ms 72156 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 860 KB Output is correct
26 Correct 2 ms 860 KB Output is correct
27 Correct 2 ms 860 KB Output is correct
28 Correct 119 ms 29104 KB Output is correct
29 Correct 214 ms 43404 KB Output is correct
30 Correct 278 ms 58096 KB Output is correct
31 Correct 388 ms 72160 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 344 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 1 ms 860 KB Output is correct
44 Correct 1 ms 904 KB Output is correct
45 Correct 161 ms 41816 KB Output is correct
46 Correct 272 ms 60748 KB Output is correct
47 Correct 263 ms 60748 KB Output is correct
48 Correct 1 ms 344 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 1 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 1 ms 344 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Incorrect 392 ms 64348 KB Solution announced impossible, but it is possible.
56 Halted 0 ms 0 KB -

Subtask #4
20.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 184 ms 47844 KB Output is correct
10 Correct 13 ms 5128 KB Output is correct
11 Correct 88 ms 25976 KB Output is correct
12 Correct 19 ms 7452 KB Output is correct
13 Correct 51 ms 15052 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 178 ms 47876 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 Correct 381 ms 83988 KB Output is correct
21 Correct 392 ms 72832 KB Output is correct
22 Correct 363 ms 83884 KB Output is correct
23 Correct 296 ms 77392 KB Output is correct
24 Correct 99 ms 20176 KB Output is correct
25 Correct 89 ms 20164 KB Output is correct
26 Correct 91 ms 20228 KB Output is correct
27 Correct 300 ms 61316 KB Output is correct
28 Correct 281 ms 61308 KB Output is correct
29 Correct 461 ms 61304 KB Output is correct
30 Correct 413 ms 61304 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 20 ms 5300 KB Output is correct
33 Correct 45 ms 10128 KB Output is correct
34 Correct 377 ms 84148 KB Output is correct
35 Correct 9 ms 2140 KB Output is correct
36 Correct 28 ms 6800 KB Output is correct
37 Correct 50 ms 11280 KB Output is correct
38 Correct 126 ms 23516 KB Output is correct
39 Correct 190 ms 32072 KB Output is correct
40 Correct 238 ms 41128 KB Output is correct
41 Correct 295 ms 49492 KB Output is correct
42 Correct 359 ms 58232 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 0 ms 348 KB Output is correct
47 Correct 1 ms 348 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 2 ms 860 KB Output is correct
55 Correct 2 ms 860 KB Output is correct
56 Correct 170 ms 41636 KB Output is correct
57 Correct 253 ms 60900 KB Output is correct
58 Correct 260 ms 60896 KB Output is correct
59 Correct 0 ms 344 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 0 ms 348 KB Output is correct
62 Correct 382 ms 89516 KB Output is correct
63 Correct 391 ms 78456 KB Output is correct
64 Correct 372 ms 83668 KB Output is correct
65 Correct 3 ms 1112 KB Output is correct
66 Correct 4 ms 1880 KB Output is correct
67 Correct 162 ms 38012 KB Output is correct
68 Correct 283 ms 57484 KB Output is correct
69 Correct 380 ms 76204 KB Output is correct

Subtask #5
20.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 184 ms 47844 KB Output is correct
10 Correct 13 ms 5128 KB Output is correct
11 Correct 88 ms 25976 KB Output is correct
12 Correct 19 ms 7452 KB Output is correct
13 Correct 51 ms 15052 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 178 ms 47876 KB Output is correct
17 Correct 392 ms 96124 KB Output is correct
18 Correct 361 ms 90756 KB Output is correct
19 Correct 352 ms 83832 KB Output is correct
20 Correct 300 ms 66228 KB Output is correct
21 Correct 291 ms 68360 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 47 ms 10200 KB Output is correct
24 Correct 16 ms 4056 KB Output is correct
25 Correct 44 ms 8984 KB Output is correct
26 Correct 67 ms 14056 KB Output is correct
27 Correct 151 ms 32680 KB Output is correct
28 Correct 196 ms 40732 KB Output is correct
29 Correct 252 ms 49140 KB Output is correct
30 Correct 296 ms 57052 KB Output is correct
31 Correct 391 ms 65416 KB Output is correct
32 Correct 401 ms 78700 KB Output is correct
33 Correct 391 ms 89468 KB Output is correct
34 Correct 4 ms 1372 KB Output is correct
35 Correct 4 ms 1628 KB Output is correct
36 Correct 153 ms 36876 KB Output is correct
37 Correct 257 ms 55616 KB Output is correct
38 Correct 344 ms 73596 KB Output is correct

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 184 ms 47844 KB Output is correct
10 Correct 13 ms 5128 KB Output is correct
11 Correct 88 ms 25976 KB Output is correct
12 Correct 19 ms 7452 KB Output is correct
13 Correct 51 ms 15052 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 178 ms 47876 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 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 380 ms 72156 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 860 KB Output is correct
26 Correct 2 ms 860 KB Output is correct
27 Correct 2 ms 860 KB Output is correct
28 Correct 119 ms 29104 KB Output is correct
29 Correct 214 ms 43404 KB Output is correct
30 Correct 278 ms 58096 KB Output is correct
31 Correct 388 ms 72160 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 344 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 1 ms 860 KB Output is correct
44 Correct 1 ms 904 KB Output is correct
45 Correct 161 ms 41816 KB Output is correct
46 Correct 272 ms 60748 KB Output is correct
47 Correct 263 ms 60748 KB Output is correct
48 Correct 1 ms 344 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 1 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 1 ms 344 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Incorrect 392 ms 64348 KB Solution announced impossible, but it is possible.
56 Halted 0 ms 0 KB -