oj.uz

Submission #1021104

# Submission time Handle Problem Language Result Execution time Memory
1021104 2024-07-12T14:06:12 Z mdn2002 Fountain Parks (IOI21_parks) C++17
5 / 100
 905 ms 142984 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);
    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;
    vector<int> u, v, a, b;

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

    for (int i = 1; i <= n; i ++) {
        if (mp[{x[i] + 2, y[i]}]) {
            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);
        }
        if (mp[{x[i], y[i] + 2}]) {
            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);
        }
    }

    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};
        for (int i = 0; i < 4; i ++) {
            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]) swap(xx, uu);
                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]) swap(xx, uu);
                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:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for (int i = 0; i < u.size(); i ++) {
      |                     ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 1 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 395 ms 71348 KB Output is correct
10 Correct 18 ms 7516 KB Output is correct
11 Correct 136 ms 38676 KB Output is correct
12 Correct 29 ms 11052 KB Output is correct
13 Correct 78 ms 24820 KB Output is correct
14 Correct 2 ms 856 KB Output is correct
15 Correct 3 ms 996 KB Output is correct
16 Correct 378 ms 71564 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 1 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 395 ms 71348 KB Output is correct
10 Correct 18 ms 7516 KB Output is correct
11 Correct 136 ms 38676 KB Output is correct
12 Correct 29 ms 11052 KB Output is correct
13 Correct 78 ms 24820 KB Output is correct
14 Correct 2 ms 856 KB Output is correct
15 Correct 3 ms 996 KB Output is correct
16 Correct 378 ms 71564 KB Output is correct
17 Incorrect 1 ms 348 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 1 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 395 ms 71348 KB Output is correct
10 Correct 18 ms 7516 KB Output is correct
11 Correct 136 ms 38676 KB Output is correct
12 Correct 29 ms 11052 KB Output is correct
13 Correct 78 ms 24820 KB Output is correct
14 Correct 2 ms 856 KB Output is correct
15 Correct 3 ms 996 KB Output is correct
16 Correct 378 ms 71564 KB Output is correct
17 Incorrect 1 ms 348 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 1 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 395 ms 71348 KB Output is correct
10 Correct 18 ms 7516 KB Output is correct
11 Correct 136 ms 38676 KB Output is correct
12 Correct 29 ms 11052 KB Output is correct
13 Correct 78 ms 24820 KB Output is correct
14 Correct 2 ms 856 KB Output is correct
15 Correct 3 ms 996 KB Output is correct
16 Correct 378 ms 71564 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 789 ms 136752 KB Output is correct
21 Correct 905 ms 142984 KB Output is correct
22 Correct 819 ms 136484 KB Output is correct
23 Correct 779 ms 125512 KB Output is correct
24 Correct 388 ms 48324 KB Output is correct
25 Correct 434 ms 57652 KB Output is correct
26 Correct 473 ms 57652 KB Output is correct
27 Correct 794 ms 76848 KB Output is correct
28 Correct 809 ms 76840 KB Output is correct
29 Runtime error 410 ms 87860 KB Execution killed with signal 6
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 1 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 395 ms 71348 KB Output is correct
10 Correct 18 ms 7516 KB Output is correct
11 Correct 136 ms 38676 KB Output is correct
12 Correct 29 ms 11052 KB Output is correct
13 Correct 78 ms 24820 KB Output is correct
14 Correct 2 ms 856 KB Output is correct
15 Correct 3 ms 996 KB Output is correct
16 Correct 378 ms 71564 KB Output is correct
17 Incorrect 454 ms 57972 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 1 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 395 ms 71348 KB Output is correct
10 Correct 18 ms 7516 KB Output is correct
11 Correct 136 ms 38676 KB Output is correct
12 Correct 29 ms 11052 KB Output is correct
13 Correct 78 ms 24820 KB Output is correct
14 Correct 2 ms 856 KB Output is correct
15 Correct 3 ms 996 KB Output is correct
16 Correct 378 ms 71564 KB Output is correct
17 Incorrect 1 ms 348 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -