oj.uz

Submission #814998

# Submission time Handle Problem Language Result Execution time Memory
814998 2023-08-08T11:37:08 Z I_Love_EliskaM_ Fountain Parks (IOI21_parks) C++17
45 / 100
 739 ms 29624 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int,int>
#define f first
#define s second

struct DSU {
	vector<int> p,sz;
	DSU(int n) {
		forn(i,n) p.pb(i), sz.pb(1);
	}
	int get(int u) {
		return p[u]==u?u:get(p[u]);
	}
	void uni(int u, int v) {
		u=get(u), v=get(v);
		if (sz[u]<sz[v]) swap(u,v);
		sz[u]+=sz[v];
		p[v]=u;
	}
};

int construct_roads(vector<int> x, vector<int> y) {
	int n=x.size();
	vector<int> u,v,a,b;
	map<pi,int> m;
	forn(i,n) m[{x[i],y[i]}]=i;
	DSU dsu(n);

	vector<pi> z={{-2,0},{2,0},{0,-2},{0,2}};
	forn(i,n) {
		int f=x[i], s=y[i];
		for(auto&x:z) {
			if (m.count({f+x.f,s+x.s})) {
				if (i<m[{f+x.f,s+x.s}]) {
					if (dsu.get(i)==dsu.get(m[{f+x.f,s+x.s}])) continue;
					dsu.uni(i,m[{f+x.f,s+x.s}]);
					u.pb(i), v.pb(m[{f+x.f,s+x.s}]);
				}
			}
		}
	}
	if (u.size()!=n-1) return 0;
	
	forn(i,n-1) {
		int x1=x[u[i]], y1=y[u[i]];
		int x2=x[v[i]], y2=y[v[i]];
		if (x1==x2) {
			if ((max(y1,y2)+x1)%4) {
				a.pb(x1+1);
				b.pb(max(y1,y2)-1);
			} else {
				a.pb(x1-1);
				b.pb(max(y1,y2)-1);
			}
		} else {
			if ((max(x1,x2)+y1)%4) {
				a.pb(max(x1,x2)-1);
				b.pb(y1-1);
			} else {
				a.pb(max(x1,x2)-1);
				b.pb(y1+1);
			}
		}
	}
	build(u,v,a,b);
	return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:47:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |  if (u.size()!=n-1) return 0;
      |      ~~~~~~~~^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 198 ms 14064 KB Output is correct
10 Correct 13 ms 1876 KB Output is correct
11 Correct 69 ms 7708 KB Output is correct
12 Correct 20 ms 2664 KB Output is correct
13 Correct 47 ms 4980 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 198 ms 14160 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 198 ms 14064 KB Output is correct
10 Correct 13 ms 1876 KB Output is correct
11 Correct 69 ms 7708 KB Output is correct
12 Correct 20 ms 2664 KB Output is correct
13 Correct 47 ms 4980 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 198 ms 14160 KB Output is correct
17 Incorrect 1 ms 212 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 2
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 198 ms 14064 KB Output is correct
10 Correct 13 ms 1876 KB Output is correct
11 Correct 69 ms 7708 KB Output is correct
12 Correct 20 ms 2664 KB Output is correct
13 Correct 47 ms 4980 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 198 ms 14160 KB Output is correct
17 Incorrect 1 ms 212 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 2
18 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 198 ms 14064 KB Output is correct
10 Correct 13 ms 1876 KB Output is correct
11 Correct 69 ms 7708 KB Output is correct
12 Correct 20 ms 2664 KB Output is correct
13 Correct 47 ms 4980 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 198 ms 14160 KB Output is correct
17 Correct 1 ms 304 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 300 KB Output is correct
20 Correct 682 ms 27540 KB Output is correct
21 Correct 720 ms 27504 KB Output is correct
22 Correct 735 ms 27476 KB Output is correct
23 Correct 514 ms 23432 KB Output is correct
24 Correct 414 ms 18248 KB Output is correct
25 Correct 728 ms 20380 KB Output is correct
26 Correct 597 ms 20432 KB Output is correct
27 Correct 606 ms 27360 KB Output is correct
28 Correct 610 ms 27392 KB Output is correct
29 Correct 739 ms 27404 KB Output is correct
30 Correct 632 ms 27376 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 23 ms 2688 KB Output is correct
33 Correct 93 ms 9640 KB Output is correct
34 Correct 516 ms 27488 KB Output is correct
35 Correct 13 ms 1468 KB Output is correct
36 Correct 97 ms 5736 KB Output is correct
37 Correct 215 ms 10620 KB Output is correct
38 Correct 186 ms 11696 KB Output is correct
39 Correct 287 ms 15452 KB Output is correct
40 Correct 400 ms 19440 KB Output is correct
41 Correct 563 ms 23440 KB Output is correct
42 Correct 727 ms 27524 KB Output is correct
43 Correct 0 ms 212 KB Output is correct
44 Correct 0 ms 212 KB Output is correct
45 Correct 1 ms 212 KB Output is correct
46 Correct 1 ms 212 KB Output is correct
47 Correct 0 ms 212 KB Output is correct
48 Correct 0 ms 212 KB Output is correct
49 Correct 1 ms 292 KB Output is correct
50 Correct 1 ms 212 KB Output is correct
51 Correct 0 ms 212 KB Output is correct
52 Correct 1 ms 212 KB Output is correct
53 Correct 1 ms 212 KB Output is correct
54 Correct 2 ms 468 KB Output is correct
55 Correct 4 ms 568 KB Output is correct
56 Correct 203 ms 14144 KB Output is correct
57 Correct 366 ms 20076 KB Output is correct
58 Correct 345 ms 20040 KB Output is correct
59 Correct 1 ms 212 KB Output is correct
60 Correct 1 ms 212 KB Output is correct
61 Correct 1 ms 300 KB Output is correct
62 Correct 473 ms 27344 KB Output is correct
63 Correct 511 ms 27380 KB Output is correct
64 Correct 543 ms 27308 KB Output is correct
65 Correct 5 ms 744 KB Output is correct
66 Correct 11 ms 1076 KB Output is correct
67 Correct 238 ms 14064 KB Output is correct
68 Correct 448 ms 20732 KB Output is correct
69 Correct 672 ms 27448 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 198 ms 14064 KB Output is correct
10 Correct 13 ms 1876 KB Output is correct
11 Correct 69 ms 7708 KB Output is correct
12 Correct 20 ms 2664 KB Output is correct
13 Correct 47 ms 4980 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 198 ms 14160 KB Output is correct
17 Correct 498 ms 27472 KB Output is correct
18 Correct 581 ms 29236 KB Output is correct
19 Correct 592 ms 29328 KB Output is correct
20 Correct 680 ms 27976 KB Output is correct
21 Correct 594 ms 25152 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 58 ms 5288 KB Output is correct
24 Correct 31 ms 2608 KB Output is correct
25 Correct 123 ms 8260 KB Output is correct
26 Correct 288 ms 13372 KB Output is correct
27 Correct 216 ms 15012 KB Output is correct
28 Correct 317 ms 18968 KB Output is correct
29 Correct 391 ms 22364 KB Output is correct
30 Correct 449 ms 25644 KB Output is correct
31 Correct 548 ms 29624 KB Output is correct
32 Correct 477 ms 28652 KB Output is correct
33 Correct 395 ms 28680 KB Output is correct
34 Correct 6 ms 852 KB Output is correct
35 Correct 12 ms 1364 KB Output is correct
36 Correct 185 ms 14620 KB Output is correct
37 Correct 318 ms 21596 KB Output is correct
38 Correct 476 ms 28652 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 198 ms 14064 KB Output is correct
10 Correct 13 ms 1876 KB Output is correct
11 Correct 69 ms 7708 KB Output is correct
12 Correct 20 ms 2664 KB Output is correct
13 Correct 47 ms 4980 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 198 ms 14160 KB Output is correct
17 Incorrect 1 ms 212 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 2
18 Halted 0 ms 0 KB -