oj.uz

Submission #1022305

# Submission time Handle Problem Language Result Execution time Memory
1022305 2024-07-13T11:58:48 Z mdn2002 Fountain Parks (IOI21_parks) C++17
55 / 100
 2435 ms 200384 KB 
/*
Mayoeba Yabureru
*/
#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
static vector<int> _u, _v, _a, _b;


int construct_roads(vector<int> x, vector<int> y) {
    int n = x.size();
    vector<vector<int>> gr(n + 1);
    vector<int> dsu(n + 1);
    map<pair<int, int>, int> mp;
    map<pair<int, int>, pair<int, int>> mpp;
    vector<pair<int, int>> vv;
    x.insert(x.begin(), 0);
    y.insert(y.begin(), 0);
    for (int i = 1; i <= n; i ++) {
        mp[{x[i], y[i]}] = i;
        vv.push_back({x[i], y[i]});
        dsu[i] = i;
    }
    vector<int> u, v, a, b;
    map<pair<int, int>, int> taken;
    map<pair<int, int>, int> connected;

    function<int(int)> fp = [&](int x) {
        if (dsu[x] == x) return x;
        return dsu[x] = fp(dsu[x]);
    };
    function cmp = [&] (pair<int, int> a, pair<int, int> b) {
        if (a.first + a.second < b.first + b.second) return 1;
        return 0;
    };
    sort(vv.begin(), vv.end(), cmp);
    for (int i = 0; i < n; i ++) {
        vector nx = {0, 0, 2, -2}, ny = {2, -2, 0, 0};
        for (int j = 0; j < 4; j ++) {
            auto xx = make_pair(vv[i].first + nx[j], vv[i].second + ny[j]);
            if (mp[xx]) {
                int fx = fp(mp[vv[i]]), fy = fp(mp[xx]);
                if (fx != fy) {
                    if (vv[i].first < xx.first || vv[i].second < xx.second) {
                        u.push_back(mp[vv[i]]);
                        v.push_back(mp[xx]);
                    }
                    else {
                        v.push_back(mp[vv[i]]);
                        u.push_back(mp[xx]);
                    }
                    gr[mp[vv[i]]].push_back(mp[xx]);
                    gr[mp[xx]].push_back(mp[vv[i]]);
                    dsu[fx] = fy;
                    connected[{mp[vv[i]], mp[xx]}] = 1;
                    connected[{mp[xx], mp[vv[i]]}] = 1;
                }
            }
        }
    }

    int num = 0, st = 1;
    vector<int> vis(n + 1);

    function<void(int)> go = [&] (int v) {
        num ++;
        vis[v] = 1;
        vector nx = {0, 2, 0, -2}, ny = {2, 0, -2, 0};
        int ii = 0;
        for (int i = 0; i < 4; i ++) {
            int u = mp[{x[v] + nx[i], y[v] + ny[i]}];
            if (u == 0) continue;
            if (vis[u]) {
                ii = (i + 1) % 4;
                break;
            }
        }
        int nummmm = 10;
        while (nummmm --) {
            int i = ii;
            ii = (ii + 1) % 4;
            int u = mp[{x[v] + nx[i], y[v] + ny[i]}];
            if (u == 0 || vis[u] || connected[{u, v}] == 0) continue;
            if (x[v] != x[u]) {
                int xx = v, uu = u;
                if (x[xx] > x[uu]) {
                    if (taken[{x[uu] + 1, y[uu] - 1}] == 0) {
                        mpp[{uu, xx}] = {x[uu] + 1, y[uu] - 1};
                        taken[{x[uu] + 1, y[uu] - 1}] = 1;
                    }
                    else if (taken[{x[uu] + 1, y[uu] + 1}] == 0) {
                        mpp[{uu, xx}] = {x[uu] + 1, y[uu] + 1};
                        taken[{x[uu] + 1, y[uu] + 1}] = 1;
                    }
                    else assert(0);
                }
                else {
                    if (taken[{x[xx] + 1, y[xx] + 1}] == 0) {
                        mpp[{xx, uu}] = {x[xx] + 1, y[xx] + 1};
                        taken[{x[xx] + 1, y[xx] + 1}] = 1;
                    }
                    else if (taken[{x[xx] + 1, y[xx] - 1}] == 0) {
                        mpp[{xx, uu}] = {x[xx] + 1, y[xx] - 1};
                        taken[{x[xx] + 1, y[xx] - 1}] = 1;
                    }
                    else assert(0);
                }
            }
            else {
                int xx = v, uu = u;
                if (y[xx] > y[uu]) {
                    if (taken[{x[uu] + 1, y[uu] + 1}] == 0) {
                        mpp[{uu, xx}] = {x[uu] + 1, y[uu] + 1};
                        taken[{x[uu] + 1, y[uu] + 1}] = 1;
                    }
                    else if (taken[{x[uu] - 1, y[uu] + 1}] == 0) {
                        mpp[{uu, xx}] = {x[uu] - 1, y[uu] + 1};
                        taken[{x[uu] - 1, y[uu] + 1}] = 1;
                    }
                    else assert(0);
                }
                else {
                    if (taken[{x[xx] - 1, y[xx] + 1}] == 0) {
                        mpp[{xx, uu}] = {x[xx] - 1, y[xx] + 1};
                        taken[{x[xx] - 1, y[xx] + 1}] = 1;
                    }
                    else if (taken[{x[xx] + 1, y[xx] + 1}] == 0) {
                        mpp[{xx, uu}] = {x[xx] + 1, y[xx] + 1};
                        taken[{x[xx] + 1, y[xx] + 1}] = 1;
                    }
                    else assert(0);
                }
            }
            go(u);
        }
    };
    go(st);
    for (int i = 0; i < u.size(); i ++) {
        a.push_back(mpp[{u[i], v[i]}].first);
        b.push_back(mpp[{u[i], v[i]}].second);
        u[i] --;
        v[i] --;
    }
    if (num == n) {
        build(u, v, a, b);
        return 1;
    }
    return 0;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 902 ms 97220 KB Output is correct
10 Correct 37 ms 10320 KB Output is correct
11 Correct 289 ms 54948 KB Output is correct
12 Correct 64 ms 15520 KB Output is correct
13 Correct 190 ms 36076 KB Output is correct
14 Correct 3 ms 860 KB Output is correct
15 Correct 6 ms 1368 KB Output is correct
16 Correct 799 ms 80676 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 902 ms 97220 KB Output is correct
10 Correct 37 ms 10320 KB Output is correct
11 Correct 289 ms 54948 KB Output is correct
12 Correct 64 ms 15520 KB Output is correct
13 Correct 190 ms 36076 KB Output is correct
14 Correct 3 ms 860 KB Output is correct
15 Correct 6 ms 1368 KB Output is correct
16 Correct 799 ms 80676 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 2041 ms 144428 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 7 ms 1116 KB Output is correct
26 Correct 10 ms 1944 KB Output is correct
27 Correct 13 ms 2140 KB Output is correct
28 Correct 727 ms 60728 KB Output is correct
29 Correct 1205 ms 83712 KB Output is correct
30 Correct 1690 ms 115028 KB Output is correct
31 Correct 2066 ms 138912 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 1 ms 344 KB Output is correct
43 Correct 7 ms 1524 KB Output is correct
44 Correct 10 ms 1884 KB Output is correct
45 Correct 815 ms 80304 KB Output is correct
46 Correct 1369 ms 118192 KB Output is correct
47 Correct 1247 ms 115468 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 902 ms 97220 KB Output is correct
10 Correct 37 ms 10320 KB Output is correct
11 Correct 289 ms 54948 KB Output is correct
12 Correct 64 ms 15520 KB Output is correct
13 Correct 190 ms 36076 KB Output is correct
14 Correct 3 ms 860 KB Output is correct
15 Correct 6 ms 1368 KB Output is correct
16 Correct 799 ms 80676 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 2041 ms 144428 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 7 ms 1116 KB Output is correct
26 Correct 10 ms 1944 KB Output is correct
27 Correct 13 ms 2140 KB Output is correct
28 Correct 727 ms 60728 KB Output is correct
29 Correct 1205 ms 83712 KB Output is correct
30 Correct 1690 ms 115028 KB Output is correct
31 Correct 2066 ms 138912 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 1 ms 344 KB Output is correct
43 Correct 7 ms 1524 KB Output is correct
44 Correct 10 ms 1884 KB Output is correct
45 Correct 815 ms 80304 KB Output is correct
46 Correct 1369 ms 118192 KB Output is correct
47 Correct 1247 ms 115468 KB Output is correct
48 Correct 1 ms 348 KB Output is correct
49 Correct 1 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 1 ms 344 KB Output is correct
53 Correct 1 ms 348 KB Output is correct
54 Correct 1 ms 348 KB Output is correct
55 Runtime error 769 ms 131656 KB Execution killed with signal 6
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 902 ms 97220 KB Output is correct
10 Correct 37 ms 10320 KB Output is correct
11 Correct 289 ms 54948 KB Output is correct
12 Correct 64 ms 15520 KB Output is correct
13 Correct 190 ms 36076 KB Output is correct
14 Correct 3 ms 860 KB Output is correct
15 Correct 6 ms 1368 KB Output is correct
16 Correct 799 ms 80676 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1757 ms 188268 KB Output is correct
21 Correct 1710 ms 171764 KB Output is correct
22 Correct 1935 ms 161684 KB Output is correct
23 Correct 1752 ms 145520 KB Output is correct
24 Correct 563 ms 48936 KB Output is correct
25 Correct 1474 ms 83484 KB Output is correct
26 Correct 1513 ms 83592 KB Output is correct
27 Correct 2220 ms 103396 KB Output is correct
28 Correct 2160 ms 103328 KB Output is correct
29 Correct 2435 ms 103472 KB Output is correct
30 Correct 2204 ms 103208 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 74 ms 10100 KB Output is correct
33 Correct 113 ms 24636 KB Output is correct
34 Correct 1599 ms 169520 KB Output is correct
35 Correct 38 ms 4700 KB Output is correct
36 Correct 246 ms 21096 KB Output is correct
37 Correct 529 ms 40772 KB Output is correct
38 Correct 642 ms 39844 KB Output is correct
39 Correct 1036 ms 54732 KB Output is correct
40 Correct 1353 ms 69304 KB Output is correct
41 Correct 1751 ms 83740 KB Output is correct
42 Correct 2183 ms 98900 KB Output is correct
43 Correct 1 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 1 ms 348 KB Output is correct
47 Correct 1 ms 344 KB Output is correct
48 Correct 1 ms 348 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 1 ms 348 KB Output is correct
51 Correct 1 ms 348 KB Output is correct
52 Correct 1 ms 348 KB Output is correct
53 Correct 1 ms 348 KB Output is correct
54 Correct 7 ms 1704 KB Output is correct
55 Correct 8 ms 1884 KB Output is correct
56 Correct 754 ms 80408 KB Output is correct
57 Correct 1256 ms 118216 KB Output is correct
58 Correct 1239 ms 115668 KB Output is correct
59 Correct 0 ms 344 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 0 ms 348 KB Output is correct
62 Correct 1870 ms 166004 KB Output is correct
63 Correct 1983 ms 173992 KB Output is correct
64 Correct 1807 ms 182668 KB Output is correct
65 Correct 17 ms 2392 KB Output is correct
66 Correct 26 ms 4176 KB Output is correct
67 Correct 727 ms 66716 KB Output is correct
68 Correct 1281 ms 107520 KB Output is correct
69 Correct 1740 ms 132772 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 902 ms 97220 KB Output is correct
10 Correct 37 ms 10320 KB Output is correct
11 Correct 289 ms 54948 KB Output is correct
12 Correct 64 ms 15520 KB Output is correct
13 Correct 190 ms 36076 KB Output is correct
14 Correct 3 ms 860 KB Output is correct
15 Correct 6 ms 1368 KB Output is correct
16 Correct 799 ms 80676 KB Output is correct
17 Correct 1880 ms 200384 KB Output is correct
18 Correct 1907 ms 151596 KB Output is correct
19 Correct 1837 ms 173640 KB Output is correct
20 Correct 1870 ms 98232 KB Output is correct
21 Correct 1911 ms 96928 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 190 ms 17660 KB Output is correct
24 Correct 117 ms 9168 KB Output is correct
25 Correct 396 ms 29652 KB Output is correct
26 Correct 649 ms 48548 KB Output is correct
27 Correct 862 ms 51008 KB Output is correct
28 Correct 1137 ms 63388 KB Output is correct
29 Correct 1421 ms 75984 KB Output is correct
30 Correct 1730 ms 88564 KB Output is correct
31 Correct 2017 ms 100996 KB Output is correct
32 Correct 1796 ms 135472 KB Output is correct
33 Correct 1914 ms 182320 KB Output is correct
34 Correct 20 ms 3152 KB Output is correct
35 Correct 33 ms 5240 KB Output is correct
36 Correct 742 ms 68568 KB Output is correct
37 Correct 1278 ms 106928 KB Output is correct
38 Correct 1953 ms 139892 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 902 ms 97220 KB Output is correct
10 Correct 37 ms 10320 KB Output is correct
11 Correct 289 ms 54948 KB Output is correct
12 Correct 64 ms 15520 KB Output is correct
13 Correct 190 ms 36076 KB Output is correct
14 Correct 3 ms 860 KB Output is correct
15 Correct 6 ms 1368 KB Output is correct
16 Correct 799 ms 80676 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 2041 ms 144428 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 7 ms 1116 KB Output is correct
26 Correct 10 ms 1944 KB Output is correct
27 Correct 13 ms 2140 KB Output is correct
28 Correct 727 ms 60728 KB Output is correct
29 Correct 1205 ms 83712 KB Output is correct
30 Correct 1690 ms 115028 KB Output is correct
31 Correct 2066 ms 138912 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 1 ms 344 KB Output is correct
43 Correct 7 ms 1524 KB Output is correct
44 Correct 10 ms 1884 KB Output is correct
45 Correct 815 ms 80304 KB Output is correct
46 Correct 1369 ms 118192 KB Output is correct
47 Correct 1247 ms 115468 KB Output is correct
48 Correct 1 ms 348 KB Output is correct
49 Correct 1 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 1 ms 344 KB Output is correct
53 Correct 1 ms 348 KB Output is correct
54 Correct 1 ms 348 KB Output is correct
55 Runtime error 769 ms 131656 KB Execution killed with signal 6
56 Halted 0 ms 0 KB -