oj.uz

Submission #443022

# Submission time Handle Problem Language Result Execution time Memory
443022 2021-07-09T13:36:12 Z benedict0724 Fountain Parks (IOI21_parks) C++17
45 / 100
 1148 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 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;
    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], y[i]+2}]) adj[i].push_back(M[{x[i], y[i]+2}]-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);
    }

    count_fountains(0);
    if(cnt < n) return 0;

    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 4884 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 434 ms 48940 KB Output is correct
10 Correct 23 ms 9420 KB Output is correct
11 Correct 127 ms 28864 KB Output is correct
12 Correct 35 ms 11676 KB Output is correct
13 Correct 79 ms 18280 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5396 KB Output is correct
16 Correct 433 ms 45660 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 4884 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 434 ms 48940 KB Output is correct
10 Correct 23 ms 9420 KB Output is correct
11 Correct 127 ms 28864 KB Output is correct
12 Correct 35 ms 11676 KB Output is correct
13 Correct 79 ms 18280 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5396 KB Output is correct
16 Correct 433 ms 45660 KB Output is correct
17 Incorrect 3 ms 4940 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
18 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 4884 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 434 ms 48940 KB Output is correct
10 Correct 23 ms 9420 KB Output is correct
11 Correct 127 ms 28864 KB Output is correct
12 Correct 35 ms 11676 KB Output is correct
13 Correct 79 ms 18280 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5396 KB Output is correct
16 Correct 433 ms 45660 KB Output is correct
17 Incorrect 3 ms 4940 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
18 Halted 0 ms 0 KB -

Subtask #4
20.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 4884 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 434 ms 48940 KB Output is correct
10 Correct 23 ms 9420 KB Output is correct
11 Correct 127 ms 28864 KB Output is correct
12 Correct 35 ms 11676 KB Output is correct
13 Correct 79 ms 18280 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5396 KB Output is correct
16 Correct 433 ms 45660 KB Output is correct
17 Correct 4 ms 4940 KB Output is correct
18 Correct 3 ms 4940 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Correct 873 ms 82240 KB Output is correct
21 Correct 932 ms 78200 KB Output is correct
22 Correct 860 ms 76408 KB Output is correct
23 Correct 798 ms 78288 KB Output is correct
24 Correct 903 ms 47428 KB Output is correct
25 Correct 966 ms 41240 KB Output is correct
26 Correct 1098 ms 41388 KB Output is correct
27 Correct 1008 ms 67732 KB Output is correct
28 Correct 1095 ms 67672 KB Output is correct
29 Correct 1148 ms 67724 KB Output is correct
30 Correct 1076 ms 67696 KB Output is correct
31 Correct 3 ms 4940 KB Output is correct
32 Correct 55 ms 9880 KB Output is correct
33 Correct 261 ms 26492 KB Output is correct
34 Correct 824 ms 82156 KB Output is correct
35 Correct 21 ms 6684 KB Output is correct
36 Correct 138 ms 13480 KB Output is correct
37 Correct 403 ms 21896 KB Output is correct
38 Correct 281 ms 28304 KB Output is correct
39 Correct 487 ms 36748 KB Output is correct
40 Correct 604 ms 46544 KB Output is correct
41 Correct 791 ms 54320 KB Output is correct
42 Correct 1107 ms 62980 KB Output is correct
43 Correct 3 ms 4924 KB Output is correct
44 Correct 3 ms 4992 KB Output is correct
45 Correct 8 ms 4996 KB Output is correct
46 Correct 3 ms 4940 KB Output is correct
47 Correct 3 ms 4940 KB Output is correct
48 Correct 3 ms 4940 KB Output is correct
49 Correct 3 ms 4992 KB Output is correct
50 Correct 3 ms 4940 KB Output is correct
51 Correct 3 ms 4940 KB Output is correct
52 Correct 8 ms 4940 KB Output is correct
53 Correct 3 ms 4940 KB Output is correct
54 Correct 15 ms 5452 KB Output is correct
55 Correct 10 ms 5580 KB Output is correct
56 Correct 465 ms 42508 KB Output is correct
57 Correct 727 ms 60548 KB Output is correct
58 Correct 691 ms 60120 KB Output is correct
59 Correct 4 ms 4940 KB Output is correct
60 Correct 3 ms 4940 KB Output is correct
61 Correct 3 ms 4888 KB Output is correct
62 Correct 1033 ms 85132 KB Output is correct
63 Correct 1006 ms 85472 KB Output is correct
64 Correct 992 ms 86680 KB Output is correct
65 Correct 9 ms 5772 KB Output is correct
66 Correct 20 ms 6532 KB Output is correct
67 Correct 396 ms 38716 KB Output is correct
68 Correct 750 ms 58252 KB Output is correct
69 Correct 1051 ms 72952 KB Output is correct

Subtask #5
20.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 4884 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 434 ms 48940 KB Output is correct
10 Correct 23 ms 9420 KB Output is correct
11 Correct 127 ms 28864 KB Output is correct
12 Correct 35 ms 11676 KB Output is correct
13 Correct 79 ms 18280 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5396 KB Output is correct
16 Correct 433 ms 45660 KB Output is correct
17 Correct 948 ms 94608 KB Output is correct
18 Correct 932 ms 88524 KB Output is correct
19 Correct 916 ms 79180 KB Output is correct
20 Correct 927 ms 65388 KB Output is correct
21 Correct 904 ms 70944 KB Output is correct
22 Correct 4 ms 4920 KB Output is correct
23 Correct 98 ms 14640 KB Output is correct
24 Correct 44 ms 8684 KB Output is correct
25 Correct 183 ms 16560 KB Output is correct
26 Correct 385 ms 24360 KB Output is correct
27 Correct 405 ms 37408 KB Output is correct
28 Correct 551 ms 45628 KB Output is correct
29 Correct 726 ms 54604 KB Output is correct
30 Correct 948 ms 61932 KB Output is correct
31 Correct 1041 ms 69964 KB Output is correct
32 Correct 1050 ms 77328 KB Output is correct
33 Correct 1088 ms 89676 KB Output is correct
34 Correct 12 ms 5964 KB Output is correct
35 Correct 21 ms 6876 KB Output is correct
36 Correct 441 ms 39524 KB Output is correct
37 Correct 768 ms 58044 KB Output is correct
38 Correct 1044 ms 73188 KB Output is correct

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 4884 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 434 ms 48940 KB Output is correct
10 Correct 23 ms 9420 KB Output is correct
11 Correct 127 ms 28864 KB Output is correct
12 Correct 35 ms 11676 KB Output is correct
13 Correct 79 ms 18280 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5396 KB Output is correct
16 Correct 433 ms 45660 KB Output is correct
17 Incorrect 3 ms 4940 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
18 Halted 0 ms 0 KB -