oj.uz

Submission #1022296

# Submission time Handle Problem Language Result Execution time Memory
1022296 2024-07-13T11:54:36 Z mdn2002 Fountain Parks (IOI21_parks) C++17
55 / 100
 2452 ms 201056 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, 2, 0, -2}, ny = {2, 0, -2, 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 857 ms 98108 KB Output is correct
10 Correct 53 ms 10580 KB Output is correct
11 Correct 296 ms 55384 KB Output is correct
12 Correct 65 ms 15696 KB Output is correct
13 Correct 223 ms 36520 KB Output is correct
14 Correct 3 ms 956 KB Output is correct
15 Correct 7 ms 1460 KB Output is correct
16 Correct 851 ms 81324 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 857 ms 98108 KB Output is correct
10 Correct 53 ms 10580 KB Output is correct
11 Correct 296 ms 55384 KB Output is correct
12 Correct 65 ms 15696 KB Output is correct
13 Correct 223 ms 36520 KB Output is correct
14 Correct 3 ms 956 KB Output is correct
15 Correct 7 ms 1460 KB Output is correct
16 Correct 851 ms 81324 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1967 ms 146040 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 7 ms 1104 KB Output is correct
26 Correct 14 ms 1836 KB Output is correct
27 Correct 13 ms 2140 KB Output is correct
28 Correct 575 ms 61400 KB Output is correct
29 Correct 1098 ms 84804 KB Output is correct
30 Correct 1508 ms 116328 KB Output is correct
31 Correct 2000 ms 140660 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 440 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 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 1 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 1 ms 344 KB Output is correct
42 Correct 1 ms 348 KB Output is correct
43 Correct 8 ms 1472 KB Output is correct
44 Correct 9 ms 1884 KB Output is correct
45 Correct 778 ms 81160 KB Output is correct
46 Correct 1259 ms 119328 KB Output is correct
47 Correct 1289 ms 116700 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 857 ms 98108 KB Output is correct
10 Correct 53 ms 10580 KB Output is correct
11 Correct 296 ms 55384 KB Output is correct
12 Correct 65 ms 15696 KB Output is correct
13 Correct 223 ms 36520 KB Output is correct
14 Correct 3 ms 956 KB Output is correct
15 Correct 7 ms 1460 KB Output is correct
16 Correct 851 ms 81324 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1967 ms 146040 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 7 ms 1104 KB Output is correct
26 Correct 14 ms 1836 KB Output is correct
27 Correct 13 ms 2140 KB Output is correct
28 Correct 575 ms 61400 KB Output is correct
29 Correct 1098 ms 84804 KB Output is correct
30 Correct 1508 ms 116328 KB Output is correct
31 Correct 2000 ms 140660 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 440 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 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 1 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 1 ms 344 KB Output is correct
42 Correct 1 ms 348 KB Output is correct
43 Correct 8 ms 1472 KB Output is correct
44 Correct 9 ms 1884 KB Output is correct
45 Correct 778 ms 81160 KB Output is correct
46 Correct 1259 ms 119328 KB Output is correct
47 Correct 1289 ms 116700 KB Output is correct
48 Correct 1 ms 344 KB Output is correct
49 Correct 1 ms 600 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 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 344 KB Output is correct
55 Runtime error 874 ms 133408 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 857 ms 98108 KB Output is correct
10 Correct 53 ms 10580 KB Output is correct
11 Correct 296 ms 55384 KB Output is correct
12 Correct 65 ms 15696 KB Output is correct
13 Correct 223 ms 36520 KB Output is correct
14 Correct 3 ms 956 KB Output is correct
15 Correct 7 ms 1460 KB Output is correct
16 Correct 851 ms 81324 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1929 ms 190716 KB Output is correct
21 Correct 1820 ms 174200 KB Output is correct
22 Correct 2071 ms 164188 KB Output is correct
23 Correct 1623 ms 147220 KB Output is correct
24 Correct 515 ms 50596 KB Output is correct
25 Correct 1358 ms 85036 KB Output is correct
26 Correct 1382 ms 85232 KB Output is correct
27 Correct 2250 ms 105112 KB Output is correct
28 Correct 2091 ms 104768 KB Output is correct
29 Correct 2414 ms 104904 KB Output is correct
30 Correct 2452 ms 104944 KB Output is correct
31 Correct 1 ms 436 KB Output is correct
32 Correct 84 ms 10276 KB Output is correct
33 Correct 111 ms 25840 KB Output is correct
34 Correct 1818 ms 172160 KB Output is correct
35 Correct 40 ms 4688 KB Output is correct
36 Correct 244 ms 21444 KB Output is correct
37 Correct 503 ms 42068 KB Output is correct
38 Correct 663 ms 40856 KB Output is correct
39 Correct 1012 ms 56304 KB Output is correct
40 Correct 1369 ms 71180 KB Output is correct
41 Correct 1653 ms 85720 KB Output is correct
42 Correct 1982 ms 101624 KB Output is correct
43 Correct 0 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 344 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 504 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 344 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 6 ms 1628 KB Output is correct
55 Correct 9 ms 1884 KB Output is correct
56 Correct 747 ms 81032 KB Output is correct
57 Correct 1248 ms 119260 KB Output is correct
58 Correct 1241 ms 116700 KB Output is correct
59 Correct 1 ms 348 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 0 ms 348 KB Output is correct
62 Correct 1853 ms 167504 KB Output is correct
63 Correct 2033 ms 174664 KB Output is correct
64 Correct 1813 ms 183452 KB Output is correct
65 Correct 14 ms 2396 KB Output is correct
66 Correct 27 ms 4180 KB Output is correct
67 Correct 709 ms 66688 KB Output is correct
68 Correct 1257 ms 108100 KB Output is correct
69 Correct 1794 ms 133340 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 857 ms 98108 KB Output is correct
10 Correct 53 ms 10580 KB Output is correct
11 Correct 296 ms 55384 KB Output is correct
12 Correct 65 ms 15696 KB Output is correct
13 Correct 223 ms 36520 KB Output is correct
14 Correct 3 ms 956 KB Output is correct
15 Correct 7 ms 1460 KB Output is correct
16 Correct 851 ms 81324 KB Output is correct
17 Correct 1903 ms 201056 KB Output is correct
18 Correct 2063 ms 152632 KB Output is correct
19 Correct 2004 ms 174780 KB Output is correct
20 Correct 2037 ms 98928 KB Output is correct
21 Correct 2108 ms 97120 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 198 ms 17596 KB Output is correct
24 Correct 95 ms 9164 KB Output is correct
25 Correct 339 ms 29436 KB Output is correct
26 Correct 657 ms 49060 KB Output is correct
27 Correct 854 ms 51404 KB Output is correct
28 Correct 1164 ms 64040 KB Output is correct
29 Correct 1421 ms 76704 KB Output is correct
30 Correct 1760 ms 89336 KB Output is correct
31 Correct 2041 ms 101956 KB Output is correct
32 Correct 1763 ms 136264 KB Output is correct
33 Correct 1939 ms 182832 KB Output is correct
34 Correct 16 ms 3164 KB Output is correct
35 Correct 32 ms 5084 KB Output is correct
36 Correct 768 ms 68668 KB Output is correct
37 Correct 1261 ms 107384 KB Output is correct
38 Correct 1811 ms 140704 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 857 ms 98108 KB Output is correct
10 Correct 53 ms 10580 KB Output is correct
11 Correct 296 ms 55384 KB Output is correct
12 Correct 65 ms 15696 KB Output is correct
13 Correct 223 ms 36520 KB Output is correct
14 Correct 3 ms 956 KB Output is correct
15 Correct 7 ms 1460 KB Output is correct
16 Correct 851 ms 81324 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1967 ms 146040 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 7 ms 1104 KB Output is correct
26 Correct 14 ms 1836 KB Output is correct
27 Correct 13 ms 2140 KB Output is correct
28 Correct 575 ms 61400 KB Output is correct
29 Correct 1098 ms 84804 KB Output is correct
30 Correct 1508 ms 116328 KB Output is correct
31 Correct 2000 ms 140660 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 440 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 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 1 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 1 ms 344 KB Output is correct
42 Correct 1 ms 348 KB Output is correct
43 Correct 8 ms 1472 KB Output is correct
44 Correct 9 ms 1884 KB Output is correct
45 Correct 778 ms 81160 KB Output is correct
46 Correct 1259 ms 119328 KB Output is correct
47 Correct 1289 ms 116700 KB Output is correct
48 Correct 1 ms 344 KB Output is correct
49 Correct 1 ms 600 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 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 344 KB Output is correct
55 Runtime error 874 ms 133408 KB Execution killed with signal 6
56 Halted 0 ms 0 KB -