oj.uz

Submission #1021233

# Submission time Handle Problem Language Result Execution time Memory
1021233 2024-07-12T16:06:57 Z mdn2002 Fountain Parks (IOI21_parks) C++17
5 / 100
 1253 ms 174800 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);
    x.insert(x.begin(), 0);
    y.insert(y.begin(), 0);
    map<pair<int, int>, int> mp;
    map<pair<int, int>, pair<int, int>> mpp;
    for (int i = 1; i <= n; i ++) {
        mp[{x[i], y[i]}] = i;
        dsu[i] = i;
    }
    vector<int> u, v, a, b;

    map<pair<int, int>, int> taken;

    function<int(int)> fp = [&](int x) {
        if (dsu[x] == x) return x;
        return dsu[x] = fp(dsu[x]);
    };
    for (int i = 1; i <= n; i ++) {
        if (mp[{x[i] + 2, y[i]}]) {
            int fx = fp(i), fy = fp(mp[{x[i] + 2, y[i]}]);
            if (fx != fy) {
                u.push_back(i), v.push_back(mp[{x[i] + 2, y[i]}]);
                gr[i].push_back(mp[{x[i] + 2, y[i]}]);
                gr[mp[{x[i] + 2, y[i]}]].push_back(i);
                dsu[fx] = fy;
            }
        }
        if (mp[{x[i], y[i] + 2}]) {
            int fx = fp(i), fy = fp(mp[{x[i] + 2, y[i]}]);
            if (fx != fy) {
                u.push_back(i), v.push_back(mp[{x[i], y[i] + 2}]);
                gr[i].push_back(mp[{x[i], y[i] + 2}]);
                gr[mp[{x[i], y[i] + 2}]].push_back(i);
                dsu[fx] = fy;
            }
        }
    }

    int num = 0, st = 0;
    vector<int> vis(n + 1);
    for (int i = 1; i <= n; i ++) {
        if (gr[i].size() == 1) {
            st = i;
            break;
        }
    }
    function<void(int)> go = [&] (int v) {
        num ++;
        vis[v] = 1;
        vector nx = {0, 2, 0, -2};
        vector 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]) 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:132:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     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 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 521 ms 88968 KB Output is correct
10 Correct 28 ms 9304 KB Output is correct
11 Correct 202 ms 48044 KB Output is correct
12 Correct 47 ms 13652 KB Output is correct
13 Correct 125 ms 29428 KB Output is correct
14 Correct 2 ms 856 KB Output is correct
15 Correct 3 ms 1112 KB Output is correct
16 Correct 478 ms 82752 KB Output is correct

Subtask #2
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 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 521 ms 88968 KB Output is correct
10 Correct 28 ms 9304 KB Output is correct
11 Correct 202 ms 48044 KB Output is correct
12 Correct 47 ms 13652 KB Output is correct
13 Correct 125 ms 29428 KB Output is correct
14 Correct 2 ms 856 KB Output is correct
15 Correct 3 ms 1112 KB Output is correct
16 Correct 478 ms 82752 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Incorrect 0 ms 348 KB a[0] = 0 is not an odd integer
20 Halted 0 ms 0 KB -

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 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 521 ms 88968 KB Output is correct
10 Correct 28 ms 9304 KB Output is correct
11 Correct 202 ms 48044 KB Output is correct
12 Correct 47 ms 13652 KB Output is correct
13 Correct 125 ms 29428 KB Output is correct
14 Correct 2 ms 856 KB Output is correct
15 Correct 3 ms 1112 KB Output is correct
16 Correct 478 ms 82752 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Incorrect 0 ms 348 KB a[0] = 0 is not an odd integer
20 Halted 0 ms 0 KB -

Subtask #4
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 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 521 ms 88968 KB Output is correct
10 Correct 28 ms 9304 KB Output is correct
11 Correct 202 ms 48044 KB Output is correct
12 Correct 47 ms 13652 KB Output is correct
13 Correct 125 ms 29428 KB Output is correct
14 Correct 2 ms 856 KB Output is correct
15 Correct 3 ms 1112 KB Output is correct
16 Correct 478 ms 82752 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 885 ms 159024 KB Given structure is not connected: There is no path between vertices 0 and 1
21 Halted 0 ms 0 KB -

Subtask #5
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 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 521 ms 88968 KB Output is correct
10 Correct 28 ms 9304 KB Output is correct
11 Correct 202 ms 48044 KB Output is correct
12 Correct 47 ms 13652 KB Output is correct
13 Correct 125 ms 29428 KB Output is correct
14 Correct 2 ms 856 KB Output is correct
15 Correct 3 ms 1112 KB Output is correct
16 Correct 478 ms 82752 KB Output is correct
17 Correct 1253 ms 174800 KB Output is correct
18 Incorrect 1138 ms 151436 KB a[7382] = 0 is not an odd integer
19 Halted 0 ms 0 KB -

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 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 521 ms 88968 KB Output is correct
10 Correct 28 ms 9304 KB Output is correct
11 Correct 202 ms 48044 KB Output is correct
12 Correct 47 ms 13652 KB Output is correct
13 Correct 125 ms 29428 KB Output is correct
14 Correct 2 ms 856 KB Output is correct
15 Correct 3 ms 1112 KB Output is correct
16 Correct 478 ms 82752 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Incorrect 0 ms 348 KB a[0] = 0 is not an odd integer
20 Halted 0 ms 0 KB -