oj.uz

Submission #809067

# Submission time Handle Problem Language Result Execution time Memory
809067 2023-08-05T15:24:21 Z puppy Fountain Parks (IOI21_parks) C++17
0 / 100
 2 ms 1364 KB 
#include "parks.h"
#include <vector>
using namespace std;
int coord[3][100005];
bool bench[4][100005];
struct UnionFind
{
    vector<int> par;
    UnionFind(int N)
    {
        par.resize(N+1);
        for (int i = 0; i <= N; i++) par[i] = i;
    }
    int fin(int v)
    {
        return v == par[v] ? v : (par[v] = fin(par[v]));
    }
    void uni(int u, int v)
    {
        par[fin(u)] = fin(v);
    }
    bool isuni(int u, int v)
    {
        return fin(u) == fin(v);
    }
};

int construct_roads(std::vector<int> x, std::vector<int> y) {
    int N = x.size();
    fill(&coord[0][0], &coord[2][100005], -1);
    for (int i = 0; i < N; i++) {
        coord[(x[i]-2)/2][y[i]/2] = i;
    }
    UnionFind uf(N);
    vector<int> u, v, a, b;
    for (int i = 1; i < 100000; i++) {
        if (coord[0][i] != -1 && coord[0][i+1] != -1) {
            uf.uni(coord[0][i], coord[0][i+1]);
            u.push_back(coord[0][i]);
            v.push_back(coord[0][i+1]);
            a.push_back(1);
            b.push_back(2*i+1);
        }
        if (coord[2][i] != -1 && coord[2][i+1] != -1) {
            uf.uni(coord[2][i], coord[2][i+1]);
            u.push_back(coord[2][i]);
            v.push_back(coord[2][i+1]);
            a.push_back(7);
            b.push_back(2*i+1);
        }
    }
    vector<pair<int, int>> edge;
    for (int i = 1; i <= 100000; i++) {
        if (coord[0][i] != -1 && coord[1][i] != -1) {
            uf.uni(coord[0][i], coord[1][i]);
            edge.push_back(make_pair(coord[0][i], coord[1][i]));
        }
        if (coord[1][i] != -1 && coord[2][i] != -1) {
            uf.uni(coord[1][i], coord[2][i]);
            edge.push_back(make_pair(coord[1][i], coord[2][i]));
        }
    }
    bool flag = false;
    for (int i = 1; i < 100000; i++) {
        if (coord[1][i] != -1 && coord[1][i+1] != -1) {
            if (uf.isuni(coord[1][i], coord[1][i+1])) continue;
            uf.uni(coord[1][i], coord[1][i+1]);
            u.push_back(coord[1][i]);
            v.push_back(coord[1][i+1]);
            b.push_back(2*i+1);
            if (!flag) a.push_back(3);
            else a.push_back(5);
            bench[a.back()/2][b.back()/2] = true;
            flag = !flag;
        }
    }
    for (pair<int, int> p:edge) {
        u.push_back(p.first);
        v.push_back(p.second);
        int xc = x[p.first] + x[p.second] >> 1;
        int yc = y[p.first];
        a.push_back(xc);
        if (bench[xc/2][(yc+1)/2]) b.push_back(yc-1);
        else b.push_back(yc+1);
        bench[a.back()/2][b.back()/2] = true;
    }
    build(u, v, a, b);
    return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:80:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         int xc = x[p.first] + x[p.second] >> 1;

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Incorrect 1 ms 1364 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Incorrect 1 ms 1364 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Incorrect 1 ms 1364 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Incorrect 1 ms 1364 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Incorrect 1 ms 1364 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Incorrect 1 ms 1364 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -