oj.uz

Submission #621002

# Submission time Handle Problem Language Result Execution time Memory
621002 2022-08-03T11:00:03 Z MKopchev Fountain Parks (IOI21_parks) C++17
15 / 100
 473 ms 47228 KB 
#include "parks.h"
#include<bits/stdc++.h>
using namespace std;

const int nmax=2e5+42;

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

map< pair<int,int>, int > seen;

int ask(int x,int y)
{
    if(seen.count({x,y}))return seen[{x,y}];

    return -1;
}

int parent[nmax];

int root(int node)
{
    if(node==parent[node])return node;

    parent[node]=root(parent[node]);

    return parent[node];
}

set< pair<int,int> > benches;

struct point
{
    int x,y,id;
};

bool cmp(point a,point b)
{
    if(a.x!=b.x)return a.x<b.x;
    return a.y<b.y;
}

point inp[nmax];

int construct_roads(std::vector<int> x, std::vector<int> y) {

    int n=x.size();

    if (n == 1) {
	build({}, {}, {}, {});
        return 1;
    }

    for(int i=0;i<x.size();i++)
        seen[{x[i],y[i]}]=i;

    for(int i=0;i<n;i++)
    {
        parent[i]=i;

        inp[i].x=x[i];
        inp[i].y=y[i];
        inp[i].id=i;
    }

    sort(inp,inp+n,cmp);

    vector<int> u={},v={},a={},b={};

    for(int j=0;j<n;j++)
    {
        int pos=ask(inp[j].x+2,inp[j].y);

        if(pos!=-1)
        {
            parent[root(pos)]=root(inp[j].id);

            u.push_back(inp[j].id);
            v.push_back(pos);

            pair<int,int> bench={inp[j].x+1,inp[j].y+1};

            if(benches.count(bench))bench.second-=2;

            a.push_back(bench.first);
            b.push_back(bench.second);

            benches.insert(bench);
        }

        pos=ask(inp[j].x,inp[j].y+2);

        if(pos!=-1)
        {
            parent[root(pos)]=root(inp[j].id);

            u.push_back(inp[j].id);
            v.push_back(pos);

            pair<int,int> bench={inp[j].x+1,inp[j].y+1};

            if(benches.count(bench))bench.first-=2;

            a.push_back(bench.first);
            b.push_back(bench.second);

            benches.insert(bench);
        }
    }

    for(int i=0;i<n;i++)
        if(root(i)!=root(0))return 0;

    build(u,v,a,b);

    return 1;
}

/*
static void check(bool cond, string message) {
	if (!cond) {
		printf("%s\n", message.c_str());
		fclose(stdout);
		exit(0);
	}
}

static int n;
static bool build_called;
static int m;
static vector<int> _u, _v, _a, _b;

void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b) {
	check(!build_called, "build is called more than once");
	build_called = true;
	m = u.size();
	check(int(v.size()) == m, "u.size() != v.size()");
	check(int(a.size()) == m, "u.size() != a.size()");
	check(int(b.size()) == m, "u.size() != b.size()");
	_u = u;
	_v = v;
	_a = a;
	_b = b;
}

int main() {
	assert(scanf("%d", &n) == 1);
	vector<int> x(n), y(n);
	for (int i = 0; i < n; i++) {
		assert(scanf("%d%d", &x[i], &y[i]) == 2);
	}
	fclose(stdin);

	build_called = false;
	const int possible = construct_roads(x, y);

	check(possible == 0 || possible == 1, "Invalid return value of construct_roads()");
	if (possible == 1) {
		check(build_called, "construct_roads() returned 1 without calling build()");
	} else {
		check(!build_called, "construct_roads() called build() but returned 0");
	}

	printf("%d\n", possible);
	if (possible == 1) {
		printf("%d\n", m);
		for (int j = 0; j < m; j++) {
			printf("%d %d %d %d\n", _u[j], _v[j], _a[j], _b[j]);
		}
	}
	fclose(stdout);
	return 0;
}
*/

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=0;i<x.size();i++)
      |                 ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 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 145 ms 19116 KB Output is correct
10 Correct 11 ms 2388 KB Output is correct
11 Correct 74 ms 10456 KB Output is correct
12 Correct 17 ms 3412 KB Output is correct
13 Correct 50 ms 7232 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 560 KB Output is correct
16 Correct 160 ms 19028 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 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 145 ms 19116 KB Output is correct
10 Correct 11 ms 2388 KB Output is correct
11 Correct 74 ms 10456 KB Output is correct
12 Correct 17 ms 3412 KB Output is correct
13 Correct 50 ms 7232 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 560 KB Output is correct
16 Correct 160 ms 19028 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 473 ms 47200 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 2 ms 596 KB Output is correct
26 Correct 3 ms 852 KB Output is correct
27 Correct 4 ms 980 KB Output is correct
28 Correct 161 ms 19064 KB Output is correct
29 Correct 281 ms 28464 KB Output is correct
30 Correct 338 ms 37884 KB Output is correct
31 Correct 435 ms 47228 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 1 ms 212 KB Output is correct
41 Correct 0 ms 212 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 3 ms 596 KB Output is correct
44 Correct 3 ms 724 KB Output is correct
45 Correct 162 ms 19116 KB Output is correct
46 Correct 234 ms 27552 KB Output is correct
47 Correct 249 ms 27464 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 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 145 ms 19116 KB Output is correct
10 Correct 11 ms 2388 KB Output is correct
11 Correct 74 ms 10456 KB Output is correct
12 Correct 17 ms 3412 KB Output is correct
13 Correct 50 ms 7232 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 560 KB Output is correct
16 Correct 160 ms 19028 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 473 ms 47200 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 2 ms 596 KB Output is correct
26 Correct 3 ms 852 KB Output is correct
27 Correct 4 ms 980 KB Output is correct
28 Correct 161 ms 19064 KB Output is correct
29 Correct 281 ms 28464 KB Output is correct
30 Correct 338 ms 37884 KB Output is correct
31 Correct 435 ms 47228 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 1 ms 212 KB Output is correct
41 Correct 0 ms 212 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 3 ms 596 KB Output is correct
44 Correct 3 ms 724 KB Output is correct
45 Correct 162 ms 19116 KB Output is correct
46 Correct 234 ms 27552 KB Output is correct
47 Correct 249 ms 27464 KB Output is correct
48 Correct 0 ms 212 KB Output is correct
49 Correct 0 ms 212 KB Output is correct
50 Incorrect 0 ms 212 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 4
51 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 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 145 ms 19116 KB Output is correct
10 Correct 11 ms 2388 KB Output is correct
11 Correct 74 ms 10456 KB Output is correct
12 Correct 17 ms 3412 KB Output is correct
13 Correct 50 ms 7232 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 560 KB Output is correct
16 Correct 160 ms 19028 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 388 ms 38700 KB Output is correct
21 Correct 403 ms 37856 KB Output is correct
22 Correct 410 ms 38124 KB Output is correct
23 Correct 279 ms 32392 KB Output is correct
24 Correct 200 ms 19088 KB Output is correct
25 Correct 334 ms 31544 KB Output is correct
26 Correct 274 ms 31600 KB Output is correct
27 Incorrect 344 ms 37880 KB Tree @(5, 3) appears more than once: for edges on positions 499 and 501
28 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 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 145 ms 19116 KB Output is correct
10 Correct 11 ms 2388 KB Output is correct
11 Correct 74 ms 10456 KB Output is correct
12 Correct 17 ms 3412 KB Output is correct
13 Correct 50 ms 7232 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 560 KB Output is correct
16 Correct 160 ms 19028 KB Output is correct
17 Correct 387 ms 37836 KB Output is correct
18 Incorrect 392 ms 37836 KB Tree @(50001, 50003) appears more than once: for edges on positions 74999 and 100001
19 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 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 145 ms 19116 KB Output is correct
10 Correct 11 ms 2388 KB Output is correct
11 Correct 74 ms 10456 KB Output is correct
12 Correct 17 ms 3412 KB Output is correct
13 Correct 50 ms 7232 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 560 KB Output is correct
16 Correct 160 ms 19028 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 473 ms 47200 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 2 ms 596 KB Output is correct
26 Correct 3 ms 852 KB Output is correct
27 Correct 4 ms 980 KB Output is correct
28 Correct 161 ms 19064 KB Output is correct
29 Correct 281 ms 28464 KB Output is correct
30 Correct 338 ms 37884 KB Output is correct
31 Correct 435 ms 47228 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 1 ms 212 KB Output is correct
41 Correct 0 ms 212 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 3 ms 596 KB Output is correct
44 Correct 3 ms 724 KB Output is correct
45 Correct 162 ms 19116 KB Output is correct
46 Correct 234 ms 27552 KB Output is correct
47 Correct 249 ms 27464 KB Output is correct
48 Correct 0 ms 212 KB Output is correct
49 Correct 0 ms 212 KB Output is correct
50 Incorrect 0 ms 212 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 4
51 Halted 0 ms 0 KB -