oj.uz

Submission #1021084

# Submission time Handle Problem Language Result Execution time Memory
1021084 2024-07-12T13:47:48 Z mdn2002 Fountain Parks (IOI21_parks) C++17
5 / 100
 740 ms 99652 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;
        for (auto u : gr[v]) {
            if (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:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     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 0 ms 344 KB Output is correct
3 Correct 1 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 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 306 ms 50240 KB Output is correct
10 Correct 14 ms 5232 KB Output is correct
11 Correct 91 ms 27340 KB Output is correct
12 Correct 23 ms 7768 KB Output is correct
13 Correct 58 ms 18212 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 305 ms 50168 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 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 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 306 ms 50240 KB Output is correct
10 Correct 14 ms 5232 KB Output is correct
11 Correct 91 ms 27340 KB Output is correct
12 Correct 23 ms 7768 KB Output is correct
13 Correct 58 ms 18212 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 305 ms 50168 KB Output is correct
17 Incorrect 0 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 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 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 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 306 ms 50240 KB Output is correct
10 Correct 14 ms 5232 KB Output is correct
11 Correct 91 ms 27340 KB Output is correct
12 Correct 23 ms 7768 KB Output is correct
13 Correct 58 ms 18212 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 305 ms 50168 KB Output is correct
17 Incorrect 0 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 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 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 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 306 ms 50240 KB Output is correct
10 Correct 14 ms 5232 KB Output is correct
11 Correct 91 ms 27340 KB Output is correct
12 Correct 23 ms 7768 KB Output is correct
13 Correct 58 ms 18212 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 305 ms 50168 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 Correct 655 ms 93360 KB Output is correct
21 Correct 740 ms 99652 KB Output is correct
22 Correct 622 ms 95792 KB Output is correct
23 Correct 584 ms 86612 KB Output is correct
24 Correct 353 ms 48136 KB Output is correct
25 Correct 467 ms 57484 KB Output is correct
26 Correct 476 ms 57540 KB Output is correct
27 Runtime error 411 ms 86580 KB Execution killed with signal 6
28 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 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 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 306 ms 50240 KB Output is correct
10 Correct 14 ms 5232 KB Output is correct
11 Correct 91 ms 27340 KB Output is correct
12 Correct 23 ms 7768 KB Output is correct
13 Correct 58 ms 18212 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 305 ms 50168 KB Output is correct
17 Incorrect 457 ms 55860 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 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 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 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 306 ms 50240 KB Output is correct
10 Correct 14 ms 5232 KB Output is correct
11 Correct 91 ms 27340 KB Output is correct
12 Correct 23 ms 7768 KB Output is correct
13 Correct 58 ms 18212 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 305 ms 50168 KB Output is correct
17 Incorrect 0 ms 348 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -