oj.uz

Submission #809082

# Submission time Handle Problem Language Result Execution time Memory
809082 2023-08-05T16:01:01 Z puppy Fountain Parks (IOI21_parks) C++17
45 / 100
 712 ms 85968 KB 
#include "parks.h"
#include <vector>
#include <map>
#include <functional>
using namespace std;
using pii = pair<int, int>;

struct UnionFind
{
    vector<int> par;
    UnionFind(int N)
    {
        par.resize(N+1);
        for (int i = 0; i <= N; i++) par[i] = i;
    }
    int fin(int v)
    {
        return v == par[v] ? v : (par[v] = fin(par[v]));
    }
    void uni(int u, int v)
    {
        par[fin(u)] = fin(v);
    }
    bool isuni(int u, int v)
    {
        return fin(u) == fin(v);
    }
};

int X[200005], Y[200005];
vector<int> adj[200005];
bool visited[200005];

pair<int, int> tilt(pair<int, int> ori, int pv)
{
    if (ori == make_pair(1, 0)) return make_pair(0, -pv);
    else if (ori == make_pair(0, 1)) return make_pair(pv, 0);
    else if (ori == make_pair(-1, 0)) return make_pair(0, pv);
    else return make_pair(-pv, 0);
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    int N = x.size();
    map<pii, int> mp;
    for (int i = 1; i <= N; i++) {
        X[i] = x[i-1], Y[i] = y[i-1];
    }
    for (int i = 1; i <= N; i++) {
        mp[make_pair(X[i], Y[i])] = i;
    }
    UnionFind uf(N);
    int dx[] = {-2, 2, 0, 0};
    int dy[] = {0, 0, -2, 2};
    for (int i = 1; i <= N; i++) {
        for (int k = 0; k < 4; k++) {
            int nx = X[i] + dx[k], ny = Y[i] + dy[k];
            int tmp = mp[make_pair(nx, ny)];
            if (tmp) {
                adj[i].push_back(tmp);
                uf.uni(i, tmp);
            }
        }
    }
    for (int i = 1; i <= N; i++) {
        if (!uf.isuni(1, i)) return 0;
    }
    vector<int> a, b, c, d;
    function<void(int, int)> dfs = [&](int v, int depth)
    {
        visited[v] = true;
        for (int i:adj[v]) {
            if (visited[i]) continue;
            int mx = X[v] + X[i] >> 1, my = Y[v] + Y[i] >> 1;
            pair<int, int> ori = make_pair((X[i] - X[v]) / 2, (Y[i] - Y[v]) / 2);
            pair<int, int> nxt = tilt(ori, (depth % 2) * 2 - 1);
            a.push_back(v-1);
            b.push_back(i-1);
            c.push_back(mx + nxt.first);
            d.push_back(my + nxt.second);
            dfs(i, depth + 1);
        }
    };
    dfs(1, 0);
    build(a, b, c, d);
    return 1;
}

Compilation message

parks.cpp: In lambda function:
parks.cpp:73:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |             int mx = X[v] + X[i] >> 1, my = Y[v] + Y[i] >> 1;
      |                      ~~~~~^~~~~~
parks.cpp:73:50: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |             int mx = X[v] + X[i] >> 1, my = Y[v] + Y[i] >> 1;
      |                                             ~~~~~^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 253 ms 44576 KB Output is correct
10 Correct 13 ms 9224 KB Output is correct
11 Correct 74 ms 26904 KB Output is correct
12 Correct 19 ms 11220 KB Output is correct
13 Correct 46 ms 16172 KB Output is correct
14 Correct 3 ms 5204 KB Output is correct
15 Correct 4 ms 5380 KB Output is correct
16 Correct 289 ms 40176 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 253 ms 44576 KB Output is correct
10 Correct 13 ms 9224 KB Output is correct
11 Correct 74 ms 26904 KB Output is correct
12 Correct 19 ms 11220 KB Output is correct
13 Correct 46 ms 16172 KB Output is correct
14 Correct 3 ms 5204 KB Output is correct
15 Correct 4 ms 5380 KB Output is correct
16 Correct 289 ms 40176 KB Output is correct
17 Incorrect 2 ms 4948 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 2
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 253 ms 44576 KB Output is correct
10 Correct 13 ms 9224 KB Output is correct
11 Correct 74 ms 26904 KB Output is correct
12 Correct 19 ms 11220 KB Output is correct
13 Correct 46 ms 16172 KB Output is correct
14 Correct 3 ms 5204 KB Output is correct
15 Correct 4 ms 5380 KB Output is correct
16 Correct 289 ms 40176 KB Output is correct
17 Incorrect 2 ms 4948 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 2
18 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 253 ms 44576 KB Output is correct
10 Correct 13 ms 9224 KB Output is correct
11 Correct 74 ms 26904 KB Output is correct
12 Correct 19 ms 11220 KB Output is correct
13 Correct 46 ms 16172 KB Output is correct
14 Correct 3 ms 5204 KB Output is correct
15 Correct 4 ms 5380 KB Output is correct
16 Correct 289 ms 40176 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 2 ms 4992 KB Output is correct
20 Correct 583 ms 75420 KB Output is correct
21 Correct 593 ms 70996 KB Output is correct
22 Correct 619 ms 68472 KB Output is correct
23 Correct 582 ms 68852 KB Output is correct
24 Correct 606 ms 49816 KB Output is correct
25 Correct 560 ms 43412 KB Output is correct
26 Correct 559 ms 43428 KB Output is correct
27 Correct 642 ms 53368 KB Output is correct
28 Correct 684 ms 53204 KB Output is correct
29 Correct 588 ms 53288 KB Output is correct
30 Correct 596 ms 53308 KB Output is correct
31 Correct 2 ms 4948 KB Output is correct
32 Correct 23 ms 9480 KB Output is correct
33 Correct 143 ms 27712 KB Output is correct
34 Correct 525 ms 71844 KB Output is correct
35 Correct 15 ms 6744 KB Output is correct
36 Correct 79 ms 13860 KB Output is correct
37 Correct 163 ms 22684 KB Output is correct
38 Correct 156 ms 23212 KB Output is correct
39 Correct 235 ms 29848 KB Output is correct
40 Correct 336 ms 36588 KB Output is correct
41 Correct 523 ms 43372 KB Output is correct
42 Correct 656 ms 50032 KB Output is correct
43 Correct 3 ms 4948 KB Output is correct
44 Correct 2 ms 4948 KB Output is correct
45 Correct 2 ms 4948 KB Output is correct
46 Correct 2 ms 4948 KB Output is correct
47 Correct 2 ms 4948 KB Output is correct
48 Correct 2 ms 4992 KB Output is correct
49 Correct 2 ms 4992 KB Output is correct
50 Correct 2 ms 4948 KB Output is correct
51 Correct 2 ms 4948 KB Output is correct
52 Correct 2 ms 4948 KB Output is correct
53 Correct 2 ms 4948 KB Output is correct
54 Correct 4 ms 5332 KB Output is correct
55 Correct 5 ms 5588 KB Output is correct
56 Correct 278 ms 38272 KB Output is correct
57 Correct 454 ms 53916 KB Output is correct
58 Correct 503 ms 53100 KB Output is correct
59 Correct 2 ms 4996 KB Output is correct
60 Correct 2 ms 4948 KB Output is correct
61 Correct 2 ms 4948 KB Output is correct
62 Correct 712 ms 75000 KB Output is correct
63 Correct 676 ms 75284 KB Output is correct
64 Correct 687 ms 77384 KB Output is correct
65 Correct 6 ms 5716 KB Output is correct
66 Correct 12 ms 6572 KB Output is correct
67 Correct 259 ms 33620 KB Output is correct
68 Correct 453 ms 50860 KB Output is correct
69 Correct 696 ms 62676 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 253 ms 44576 KB Output is correct
10 Correct 13 ms 9224 KB Output is correct
11 Correct 74 ms 26904 KB Output is correct
12 Correct 19 ms 11220 KB Output is correct
13 Correct 46 ms 16172 KB Output is correct
14 Correct 3 ms 5204 KB Output is correct
15 Correct 4 ms 5380 KB Output is correct
16 Correct 289 ms 40176 KB Output is correct
17 Correct 665 ms 85968 KB Output is correct
18 Correct 692 ms 85888 KB Output is correct
19 Correct 578 ms 75716 KB Output is correct
20 Correct 539 ms 56240 KB Output is correct
21 Correct 562 ms 59096 KB Output is correct
22 Correct 2 ms 4948 KB Output is correct
23 Correct 52 ms 13204 KB Output is correct
24 Correct 26 ms 8280 KB Output is correct
25 Correct 108 ms 16716 KB Output is correct
26 Correct 205 ms 24960 KB Output is correct
27 Correct 225 ms 30952 KB Output is correct
28 Correct 320 ms 37664 KB Output is correct
29 Correct 399 ms 44032 KB Output is correct
30 Correct 484 ms 50460 KB Output is correct
31 Correct 570 ms 56988 KB Output is correct
32 Correct 639 ms 70160 KB Output is correct
33 Correct 695 ms 81356 KB Output is correct
34 Correct 7 ms 5904 KB Output is correct
35 Correct 15 ms 6736 KB Output is correct
36 Correct 246 ms 35288 KB Output is correct
37 Correct 456 ms 51084 KB Output is correct
38 Correct 650 ms 66568 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 253 ms 44576 KB Output is correct
10 Correct 13 ms 9224 KB Output is correct
11 Correct 74 ms 26904 KB Output is correct
12 Correct 19 ms 11220 KB Output is correct
13 Correct 46 ms 16172 KB Output is correct
14 Correct 3 ms 5204 KB Output is correct
15 Correct 4 ms 5380 KB Output is correct
16 Correct 289 ms 40176 KB Output is correct
17 Incorrect 2 ms 4948 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 2
18 Halted 0 ms 0 KB -