oj.uz

Submission #443049

# Submission time Handle Problem Language Result Execution time Memory
443049 2021-07-09T14:16:22 Z benedict0724 Fountain Parks (IOI21_parks) C++17
5 / 100
 1213 ms 94608 KB 
#include "parks.h"

#include <bits/stdc++.h>
using namespace std;

map<pair<int, int>, int> M, M2;
vector<int> adj[200000];
bool counting[200000];

vector<pair<int, int>> E;

int link[200002];

int _find(int x)
{
    if(x == link[x]) return x;
    return link[x] = _find(link[x]);
}

void _unite(int x, int y)
{
    x = _find(x); y = _find(y);
    link[x] = y;
}

int cnt = 0;
void count_fountains(int x)
{
    cnt++;
    counting[x] = true;
    for(int i : adj[x])
    {
        if(counting[i]) continue;
        count_fountains(i);
        E.push_back({x, i});
    }
}

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

    if (x.size() == 1) {
	build({}, {}, {}, {});
        return 1;
    }

    int n = x.size();
    vector<int> u, v, a, b;

    int MAX = 0;
    for(int i=0;i<n;i++) MAX = max(MAX, x[i]);

    for(int i=0;i<n;i++)
        M[{x[i], y[i]}] = i+1;

    for(int i=0;i<n;i++)
    {
        if(M[{x[i]+2, y[i]}]) adj[i].push_back(M[{x[i]+2, y[i]}]-1);
        if(M[{x[i]-2, y[i]}]) adj[i].push_back(M[{x[i]-2, y[i]}]-1);
        if(M[{x[i], y[i]+2}]) adj[i].push_back(M[{x[i], y[i]+2}]-1);
        if(M[{x[i], y[i]-2}]) adj[i].push_back(M[{x[i], y[i]-2}]-1);
    }

    count_fountains(0);

    if(cnt < n) return 0;

    if(MAX <= 6)
    {
        for(int i=0;i<n;i++) link[i] = i;
        for(int i=0;i<n;i++)
        {
            for(int j : adj[i])
            {
                if(y[i] < y[j])
                {
                    u.push_back(i);
                    v.push_back(j);
                    b.push_back(y[i] + 1);
                    if(x[i] == 2 || (x[i] == 4 && y[i]%4 == 0))
                    {
                        a.push_back(x[i] - 1);
                        M2[{x[i]-1,y[i]+1}] = 1;
                    }

                    else
                    {
                        a.push_back(x[i] + 1);
                        M2[{x[i]+1, y[i]+1}] = 1;
                    }

                    _unite(i, j);
                }
            }
        }
        for(int i=0;i<n;i++)
        {
            for(int j : adj[i])
            {
                if(_find(i) == _find(j)) continue;
                if(x[i] > x[j]) swap(i, j);
                u.push_back(i);
                v.push_back(j);
                a.push_back(x[i] + 1);
                if(M2[{x[i] + 1, y[i] + 1}]) b.push_back(y[i] - 1);
                else b.push_back(y[i] + 1);

                _unite(i, j);
            }
        }

        build(u, v, a, b);
        return 1;
    }

    for(auto U : E)
    {
        int i = U.first, j = U.second;
        if(x[i] == x[j]) continue;
        if(x[i] > x[j]) swap(i, j);
        u.push_back(i);
        v.push_back(j);
        a.push_back(x[i]+1);
        if((x[i]+y[i])%4 == 0)
        {
            b.push_back(y[i]+1);
            M2[{x[i]+1, y[i]+1}] = 1;
        }
        else
        {
            b.push_back(y[i]-1);
            M2[{x[i]+1, y[i]-1}] = 1;
        }
    }

    for(auto U : E)
    {
        int i = U.first, j = U.second;
        if(x[i] != x[j]) continue;
        if(y[i] > y[j]) swap(i, j);
        u.push_back(i);
        v.push_back(j);
        b.push_back(y[i]+1);
        if(M2[{x[i]+1, y[i]+1}]) a.push_back(x[i]-1);
        else a.push_back(x[i]+1);
    }

    build(u, v, a, b);
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 419 ms 49248 KB Output is correct
10 Correct 23 ms 9528 KB Output is correct
11 Correct 141 ms 29064 KB Output is correct
12 Correct 33 ms 11708 KB Output is correct
13 Correct 79 ms 18128 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5452 KB Output is correct
16 Correct 387 ms 46124 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 419 ms 49248 KB Output is correct
10 Correct 23 ms 9528 KB Output is correct
11 Correct 141 ms 29064 KB Output is correct
12 Correct 33 ms 11708 KB Output is correct
13 Correct 79 ms 18128 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5452 KB Output is correct
16 Correct 387 ms 46124 KB Output is correct
17 Correct 4 ms 5000 KB Output is correct
18 Correct 3 ms 4940 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Correct 3 ms 4940 KB Output is correct
21 Correct 3 ms 4940 KB Output is correct
22 Correct 4 ms 4996 KB Output is correct
23 Correct 986 ms 80760 KB Output is correct
24 Correct 3 ms 4940 KB Output is correct
25 Correct 5 ms 5364 KB Output is correct
26 Correct 9 ms 5580 KB Output is correct
27 Correct 10 ms 5708 KB Output is correct
28 Correct 407 ms 35812 KB Output is correct
29 Correct 593 ms 49092 KB Output is correct
30 Correct 801 ms 66196 KB Output is correct
31 Correct 1213 ms 79364 KB Output is correct
32 Correct 3 ms 4940 KB Output is correct
33 Correct 4 ms 4940 KB Output is correct
34 Correct 3 ms 4940 KB Output is correct
35 Correct 3 ms 4940 KB Output is correct
36 Correct 3 ms 4940 KB Output is correct
37 Correct 4 ms 4940 KB Output is correct
38 Correct 3 ms 4940 KB Output is correct
39 Correct 3 ms 4940 KB Output is correct
40 Correct 3 ms 4940 KB Output is correct
41 Correct 3 ms 4940 KB Output is correct
42 Correct 3 ms 4940 KB Output is correct
43 Correct 6 ms 5452 KB Output is correct
44 Correct 7 ms 5620 KB Output is correct
45 Incorrect 431 ms 41676 KB Given structure is not connected: There is no path between vertices 0 and 1
46 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 419 ms 49248 KB Output is correct
10 Correct 23 ms 9528 KB Output is correct
11 Correct 141 ms 29064 KB Output is correct
12 Correct 33 ms 11708 KB Output is correct
13 Correct 79 ms 18128 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5452 KB Output is correct
16 Correct 387 ms 46124 KB Output is correct
17 Correct 4 ms 5000 KB Output is correct
18 Correct 3 ms 4940 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Correct 3 ms 4940 KB Output is correct
21 Correct 3 ms 4940 KB Output is correct
22 Correct 4 ms 4996 KB Output is correct
23 Correct 986 ms 80760 KB Output is correct
24 Correct 3 ms 4940 KB Output is correct
25 Correct 5 ms 5364 KB Output is correct
26 Correct 9 ms 5580 KB Output is correct
27 Correct 10 ms 5708 KB Output is correct
28 Correct 407 ms 35812 KB Output is correct
29 Correct 593 ms 49092 KB Output is correct
30 Correct 801 ms 66196 KB Output is correct
31 Correct 1213 ms 79364 KB Output is correct
32 Correct 3 ms 4940 KB Output is correct
33 Correct 4 ms 4940 KB Output is correct
34 Correct 3 ms 4940 KB Output is correct
35 Correct 3 ms 4940 KB Output is correct
36 Correct 3 ms 4940 KB Output is correct
37 Correct 4 ms 4940 KB Output is correct
38 Correct 3 ms 4940 KB Output is correct
39 Correct 3 ms 4940 KB Output is correct
40 Correct 3 ms 4940 KB Output is correct
41 Correct 3 ms 4940 KB Output is correct
42 Correct 3 ms 4940 KB Output is correct
43 Correct 6 ms 5452 KB Output is correct
44 Correct 7 ms 5620 KB Output is correct
45 Incorrect 431 ms 41676 KB Given structure is not connected: There is no path between vertices 0 and 1
46 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 419 ms 49248 KB Output is correct
10 Correct 23 ms 9528 KB Output is correct
11 Correct 141 ms 29064 KB Output is correct
12 Correct 33 ms 11708 KB Output is correct
13 Correct 79 ms 18128 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5452 KB Output is correct
16 Correct 387 ms 46124 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 3 ms 4912 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Correct 820 ms 82192 KB Output is correct
21 Correct 834 ms 75888 KB Output is correct
22 Correct 920 ms 74064 KB Output is correct
23 Correct 729 ms 76484 KB Output is correct
24 Correct 755 ms 45772 KB Output is correct
25 Correct 722 ms 39652 KB Output is correct
26 Correct 726 ms 39868 KB Output is correct
27 Correct 975 ms 66228 KB Output is correct
28 Correct 910 ms 66220 KB Output is correct
29 Correct 851 ms 66200 KB Output is correct
30 Correct 930 ms 66128 KB Output is correct
31 Correct 3 ms 4940 KB Output is correct
32 Correct 42 ms 9780 KB Output is correct
33 Correct 207 ms 25244 KB Output is correct
34 Correct 871 ms 79632 KB Output is correct
35 Correct 21 ms 6604 KB Output is correct
36 Correct 119 ms 12844 KB Output is correct
37 Correct 316 ms 20632 KB Output is correct
38 Correct 266 ms 27200 KB Output is correct
39 Correct 436 ms 35244 KB Output is correct
40 Correct 560 ms 44788 KB Output is correct
41 Correct 796 ms 52244 KB Output is correct
42 Correct 923 ms 60552 KB Output is correct
43 Correct 4 ms 4940 KB Output is correct
44 Correct 3 ms 4940 KB Output is correct
45 Correct 3 ms 4940 KB Output is correct
46 Correct 3 ms 4940 KB Output is correct
47 Correct 4 ms 4940 KB Output is correct
48 Correct 3 ms 4940 KB Output is correct
49 Correct 3 ms 4940 KB Output is correct
50 Correct 3 ms 4940 KB Output is correct
51 Correct 3 ms 4940 KB Output is correct
52 Correct 3 ms 4940 KB Output is correct
53 Correct 3 ms 4940 KB Output is correct
54 Correct 6 ms 5452 KB Output is correct
55 Correct 7 ms 5532 KB Output is correct
56 Incorrect 459 ms 41720 KB Given structure is not connected: There is no path between vertices 0 and 1
57 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 419 ms 49248 KB Output is correct
10 Correct 23 ms 9528 KB Output is correct
11 Correct 141 ms 29064 KB Output is correct
12 Correct 33 ms 11708 KB Output is correct
13 Correct 79 ms 18128 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5452 KB Output is correct
16 Correct 387 ms 46124 KB Output is correct
17 Correct 924 ms 94608 KB Output is correct
18 Correct 872 ms 88540 KB Output is correct
19 Correct 814 ms 79232 KB Output is correct
20 Correct 853 ms 62548 KB Output is correct
21 Correct 793 ms 67776 KB Output is correct
22 Correct 3 ms 4940 KB Output is correct
23 Correct 90 ms 14164 KB Output is correct
24 Correct 42 ms 8380 KB Output is correct
25 Correct 182 ms 15612 KB Output is correct
26 Correct 365 ms 22848 KB Output is correct
27 Correct 364 ms 34988 KB Output is correct
28 Correct 486 ms 42364 KB Output is correct
29 Correct 590 ms 50900 KB Output is correct
30 Correct 759 ms 57756 KB Output is correct
31 Correct 906 ms 65096 KB Output is correct
32 Incorrect 1002 ms 76708 KB Given structure is not connected: There is no path between vertices 0 and 15
33 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 419 ms 49248 KB Output is correct
10 Correct 23 ms 9528 KB Output is correct
11 Correct 141 ms 29064 KB Output is correct
12 Correct 33 ms 11708 KB Output is correct
13 Correct 79 ms 18128 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5452 KB Output is correct
16 Correct 387 ms 46124 KB Output is correct
17 Correct 4 ms 5000 KB Output is correct
18 Correct 3 ms 4940 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Correct 3 ms 4940 KB Output is correct
21 Correct 3 ms 4940 KB Output is correct
22 Correct 4 ms 4996 KB Output is correct
23 Correct 986 ms 80760 KB Output is correct
24 Correct 3 ms 4940 KB Output is correct
25 Correct 5 ms 5364 KB Output is correct
26 Correct 9 ms 5580 KB Output is correct
27 Correct 10 ms 5708 KB Output is correct
28 Correct 407 ms 35812 KB Output is correct
29 Correct 593 ms 49092 KB Output is correct
30 Correct 801 ms 66196 KB Output is correct
31 Correct 1213 ms 79364 KB Output is correct
32 Correct 3 ms 4940 KB Output is correct
33 Correct 4 ms 4940 KB Output is correct
34 Correct 3 ms 4940 KB Output is correct
35 Correct 3 ms 4940 KB Output is correct
36 Correct 3 ms 4940 KB Output is correct
37 Correct 4 ms 4940 KB Output is correct
38 Correct 3 ms 4940 KB Output is correct
39 Correct 3 ms 4940 KB Output is correct
40 Correct 3 ms 4940 KB Output is correct
41 Correct 3 ms 4940 KB Output is correct
42 Correct 3 ms 4940 KB Output is correct
43 Correct 6 ms 5452 KB Output is correct
44 Correct 7 ms 5620 KB Output is correct
45 Incorrect 431 ms 41676 KB Given structure is not connected: There is no path between vertices 0 and 1
46 Halted 0 ms 0 KB -