oj.uz

Submission #623457

# Submission time Handle Problem Language Result Execution time Memory
623457 2022-08-05T15:54:26 Z cheissmart Fountain Parks (IOI21_parks) C++17
0 / 100
 1 ms 212 KB 
#include "parks.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

int dx[] = {0, 0, 2, -2}, dy[] = {2, -2, 0, 0};

int construct_roads(vi x, vi y) {
    int n = SZ(x);
    map<pi, int> mp;
    for(int i = 0; i < n; i++)
        mp[{x[i], y[i]}] = i;

    V<pi> edges;
    set<pi> vis;
    function<void(int, int)> dfs = [&] (int X, int Y) {
        vis.insert({X, Y});
        for(int i = 0; i < 4; i++) {
            int xx = X + dx[i], yy = Y + dy[i];
            if(mp.count({xx, yy}) && !vis.count({xx, yy})) {
                edges.EB(mp[{X, Y}], mp[{xx, yy}]);
                dfs(xx, yy);
            }
        }
    };
    if(SZ(vis) != n) return 0;

    vi u, v, a, b;
    for(int i = 0; i < n - 1; i++) {
        u.PB(edges[i].F), v.PB(edges[i].S);
        int X = (x[edges[i].F] + x[edges[i].S]) / 2;
        int Y = (y[edges[i].F] + y[edges[i].S]) / 2;
        if(x[edges[i].F] == x[edges[i].S]) { // vertical
            if(X == 2) X--;
            else X++;
        } else { // horizontal
            Y--;
        }
        a.PB(X), b.PB(Y);
    }
    build(u, v, a, b);
    return 1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -