oj.uz

Submission #1022392

# Submission time Handle Problem Language Result Execution time Memory
1022392 2024-07-13T12:40:03 Z mdn2002 Fountain Parks (IOI21_parks) C++17
15 / 100
 2571 ms 323296 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}, ny = {2, -2};
        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;
                }
            }
        }
    }
    for (int i = 0; i < n; i ++) {
        vector nx = {2, -2}, ny = {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);
    for (int i = 1; i <= n; i ++) {
        if (mp[{x[i], y[i] + 2}]) {
            st = i;
            break;
        }
    }

    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]) {
                    int ad = y[uu] % 4;
                    if (ad == 2) ad = 1;
                    else ad = -1;
                    if (taken[{x[uu] + ad, y[uu] + 1}] == 0) {
                        mpp[{uu, xx}] = {x[uu] + ad, y[uu] + 1};
                        taken[{x[uu] + ad, y[uu] + 1}] = 1;
                    }
                    else if (taken[{x[uu] - ad, y[uu] + 1}] == 0) {
                        mpp[{uu, xx}] = {x[uu] - ad, y[uu] + 1};
                        taken[{x[uu] - ad, y[uu] + 1}] = 1;
                    }
                    else assert(0);
                }
                else {
                    int ad = y[uu] % 4;
                    if (ad == 2) ad = 1;
                    else ad = -1;
                    if (taken[{x[xx] - ad, y[xx] + 1}] == 0) {
                        mpp[{xx, uu}] = {x[xx] - ad, y[xx] + 1};
                        taken[{x[xx] - ad, y[xx] + 1}] = 1;
                    }
                    else if (taken[{x[xx] + ad, y[xx] + 1}] == 0) {
                        mpp[{xx, uu}] = {x[xx] + ad, y[xx] + 1};
                        taken[{x[xx] + ad, 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:173:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |     for (int i = 0; i < u.size(); i ++) {
      |                     ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 797 ms 99636 KB Output is correct
10 Correct 48 ms 10576 KB Output is correct
11 Correct 313 ms 56092 KB Output is correct
12 Correct 80 ms 15776 KB Output is correct
13 Correct 224 ms 36784 KB Output is correct
14 Correct 3 ms 856 KB Output is correct
15 Correct 7 ms 1372 KB Output is correct
16 Correct 745 ms 82080 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 797 ms 99636 KB Output is correct
10 Correct 48 ms 10576 KB Output is correct
11 Correct 313 ms 56092 KB Output is correct
12 Correct 80 ms 15776 KB Output is correct
13 Correct 224 ms 36784 KB Output is correct
14 Correct 3 ms 856 KB Output is correct
15 Correct 7 ms 1372 KB Output is correct
16 Correct 745 ms 82080 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 436 KB Output is correct
23 Correct 1824 ms 190740 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 6 ms 1588 KB Output is correct
26 Correct 11 ms 2140 KB Output is correct
27 Correct 12 ms 2396 KB Output is correct
28 Correct 641 ms 80044 KB Output is correct
29 Correct 1069 ms 100040 KB Output is correct
30 Correct 1428 ms 127516 KB Output is correct
31 Correct 1772 ms 187388 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 1 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 0 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 348 KB Output is correct
43 Correct 7 ms 1532 KB Output is correct
44 Correct 10 ms 1884 KB Output is correct
45 Correct 755 ms 81984 KB Output is correct
46 Correct 1348 ms 120836 KB Output is correct
47 Correct 1332 ms 118532 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 797 ms 99636 KB Output is correct
10 Correct 48 ms 10576 KB Output is correct
11 Correct 313 ms 56092 KB Output is correct
12 Correct 80 ms 15776 KB Output is correct
13 Correct 224 ms 36784 KB Output is correct
14 Correct 3 ms 856 KB Output is correct
15 Correct 7 ms 1372 KB Output is correct
16 Correct 745 ms 82080 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 436 KB Output is correct
23 Correct 1824 ms 190740 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 6 ms 1588 KB Output is correct
26 Correct 11 ms 2140 KB Output is correct
27 Correct 12 ms 2396 KB Output is correct
28 Correct 641 ms 80044 KB Output is correct
29 Correct 1069 ms 100040 KB Output is correct
30 Correct 1428 ms 127516 KB Output is correct
31 Correct 1772 ms 187388 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 1 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 0 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 348 KB Output is correct
43 Correct 7 ms 1532 KB Output is correct
44 Correct 10 ms 1884 KB Output is correct
45 Correct 755 ms 81984 KB Output is correct
46 Correct 1348 ms 120836 KB Output is correct
47 Correct 1332 ms 118532 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 0 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 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Correct 2104 ms 157724 KB Output is correct
56 Correct 1 ms 348 KB Output is correct
57 Correct 8 ms 1656 KB Output is correct
58 Correct 31 ms 5204 KB Output is correct
59 Correct 37 ms 4968 KB Output is correct
60 Correct 951 ms 70604 KB Output is correct
61 Correct 1298 ms 109180 KB Output is correct
62 Correct 1664 ms 130352 KB Output is correct
63 Correct 2250 ms 147348 KB Output is correct
64 Correct 0 ms 348 KB Output is correct
65 Correct 0 ms 348 KB Output is correct
66 Correct 1 ms 348 KB Output is correct
67 Correct 1931 ms 169700 KB Output is correct
68 Correct 1965 ms 176944 KB Output is correct
69 Correct 1893 ms 185908 KB Output is correct
70 Runtime error 15 ms 4440 KB Execution killed with signal 6
71 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 797 ms 99636 KB Output is correct
10 Correct 48 ms 10576 KB Output is correct
11 Correct 313 ms 56092 KB Output is correct
12 Correct 80 ms 15776 KB Output is correct
13 Correct 224 ms 36784 KB Output is correct
14 Correct 3 ms 856 KB Output is correct
15 Correct 7 ms 1372 KB Output is correct
16 Correct 745 ms 82080 KB Output is correct
17 Correct 1 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 2571 ms 191788 KB Output is correct
21 Correct 2068 ms 174092 KB Output is correct
22 Correct 2502 ms 166064 KB Output is correct
23 Correct 1675 ms 148484 KB Output is correct
24 Correct 791 ms 50940 KB Output is correct
25 Correct 1604 ms 85024 KB Output is correct
26 Correct 1442 ms 85124 KB Output is correct
27 Correct 2146 ms 104964 KB Output is correct
28 Correct 2024 ms 104816 KB Output is correct
29 Correct 2472 ms 104748 KB Output is correct
30 Correct 2465 ms 104832 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Runtime error 64 ms 10760 KB Execution killed with signal 6
33 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 797 ms 99636 KB Output is correct
10 Correct 48 ms 10576 KB Output is correct
11 Correct 313 ms 56092 KB Output is correct
12 Correct 80 ms 15776 KB Output is correct
13 Correct 224 ms 36784 KB Output is correct
14 Correct 3 ms 856 KB Output is correct
15 Correct 7 ms 1372 KB Output is correct
16 Correct 745 ms 82080 KB Output is correct
17 Correct 2066 ms 197512 KB Output is correct
18 Correct 2005 ms 176944 KB Output is correct
19 Runtime error 1998 ms 323296 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 797 ms 99636 KB Output is correct
10 Correct 48 ms 10576 KB Output is correct
11 Correct 313 ms 56092 KB Output is correct
12 Correct 80 ms 15776 KB Output is correct
13 Correct 224 ms 36784 KB Output is correct
14 Correct 3 ms 856 KB Output is correct
15 Correct 7 ms 1372 KB Output is correct
16 Correct 745 ms 82080 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 436 KB Output is correct
23 Correct 1824 ms 190740 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 6 ms 1588 KB Output is correct
26 Correct 11 ms 2140 KB Output is correct
27 Correct 12 ms 2396 KB Output is correct
28 Correct 641 ms 80044 KB Output is correct
29 Correct 1069 ms 100040 KB Output is correct
30 Correct 1428 ms 127516 KB Output is correct
31 Correct 1772 ms 187388 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 1 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 0 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 348 KB Output is correct
43 Correct 7 ms 1532 KB Output is correct
44 Correct 10 ms 1884 KB Output is correct
45 Correct 755 ms 81984 KB Output is correct
46 Correct 1348 ms 120836 KB Output is correct
47 Correct 1332 ms 118532 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 0 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 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Correct 2104 ms 157724 KB Output is correct
56 Correct 1 ms 348 KB Output is correct
57 Correct 8 ms 1656 KB Output is correct
58 Correct 31 ms 5204 KB Output is correct
59 Correct 37 ms 4968 KB Output is correct
60 Correct 951 ms 70604 KB Output is correct
61 Correct 1298 ms 109180 KB Output is correct
62 Correct 1664 ms 130352 KB Output is correct
63 Correct 2250 ms 147348 KB Output is correct
64 Correct 0 ms 348 KB Output is correct
65 Correct 0 ms 348 KB Output is correct
66 Correct 1 ms 348 KB Output is correct
67 Correct 1931 ms 169700 KB Output is correct
68 Correct 1965 ms 176944 KB Output is correct
69 Correct 1893 ms 185908 KB Output is correct
70 Runtime error 15 ms 4440 KB Execution killed with signal 6
71 Halted 0 ms 0 KB -