oj.uz

Submission #446389

# Submission time Handle Problem Language Result Execution time Memory
446389 2021-07-21T20:26:54 Z luciocf Fountain Parks (IOI21_parks) C++17
5 / 100
 196 ms 22028 KB 
#include <bits/stdc++.h>
#include "parks.h"

using namespace std;

const int maxn = 2e5+10;

struct Pt
{
    int x, y, ind;
} a[maxn];

struct Road
{
    int u, v, x, y;
} road[maxn];

struct DSU
{
    int pai[maxn], peso[maxn];

    void init(int n)
    {
        for (int i = 1; i <= n; i++)
            pai[i] = i;
    }

    int Find(int x)
    {
        if (pai[x] == x) return x;
        return pai[x] = Find(pai[x]);
    }

    void Join(int x, int y)
    {
        if (x == y) return;

        if (peso[x] < peso[y]) swap(x, y);

        pai[y] = x, peso[x] += peso[y]; 
    }
} dsu;

bool comp(Pt a, Pt b)
{
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

bool comp2(Pt a, Pt b)
{
    if (a.y == b.y) return a.x < b.x;
    return a.y < b.y;
}

int construct_roads(vector<int> X, vector<int> Y)
{
    int n = X.size();
    bool sub = 1;

    for (int i = 1; i <= n; i++)
    {
        a[i] = {X[i-1], Y[i-1], i};

        if (a[i].x > 6) sub = 0;
    }

    dsu.init(n);

    if (sub)
    {
        sort(a+1, a+n+1, comp);

        int ind = 0, cc = n;

        for (int i = 1; i < n; i++)
        {
            if (a[i].x == a[i+1].x && a[i].y+2 == a[i+1].y)
            {
                dsu.Join(a[i].ind, a[i+1].ind), cc--;
                road[++ind] = {a[i].ind, a[i+1].ind, a[i].x-1, a[i].y+1};
            }
        }

        sort(a+1, a+n+1, comp2);

        for (int i = 1; i < n; i++)
        {
            if (dsu.Find(a[i].ind) != dsu.Find(a[i+1].ind) && a[i].y == a[i+1].y && a[i].x+2 == a[i+1].x)
            {
                dsu.Join(a[i].ind, a[i+1].ind), cc--;
                road[++ind] = {a[i].ind, a[i+1].ind, a[i].x+1, a[i].y+1};
            }
        }

        if (cc != 1) return 0;

        vector<int> U, V, A, B;

        for (int i = 1; i < n; i++)
        {
            U.push_back(road[i].u-1), V.push_back(road[i].v-1);
            A.push_back(road[i].x), B.push_back(road[i].y);
        }

        build(U, V, A, B);
        return 1;
    }
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:109:1: warning: control reaches end of non-void function [-Wreturn-type]
  109 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 82 ms 11024 KB Output is correct
10 Correct 7 ms 1612 KB Output is correct
11 Correct 39 ms 6176 KB Output is correct
12 Correct 12 ms 2148 KB Output is correct
13 Correct 15 ms 2940 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 440 KB Output is correct
16 Correct 82 ms 11024 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 82 ms 11024 KB Output is correct
10 Correct 7 ms 1612 KB Output is correct
11 Correct 39 ms 6176 KB Output is correct
12 Correct 12 ms 2148 KB Output is correct
13 Correct 15 ms 2940 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 440 KB Output is correct
16 Correct 82 ms 11024 KB Output is correct
17 Incorrect 0 ms 204 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 2
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 82 ms 11024 KB Output is correct
10 Correct 7 ms 1612 KB Output is correct
11 Correct 39 ms 6176 KB Output is correct
12 Correct 12 ms 2148 KB Output is correct
13 Correct 15 ms 2940 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 440 KB Output is correct
16 Correct 82 ms 11024 KB Output is correct
17 Incorrect 0 ms 204 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 2
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 82 ms 11024 KB Output is correct
10 Correct 7 ms 1612 KB Output is correct
11 Correct 39 ms 6176 KB Output is correct
12 Correct 12 ms 2148 KB Output is correct
13 Correct 15 ms 2940 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 440 KB Output is correct
16 Correct 82 ms 11024 KB Output is correct
17 Incorrect 1 ms 204 KB Tree @(199999, 3) appears more than once: for edges on positions 0 and 1
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 82 ms 11024 KB Output is correct
10 Correct 7 ms 1612 KB Output is correct
11 Correct 39 ms 6176 KB Output is correct
12 Correct 12 ms 2148 KB Output is correct
13 Correct 15 ms 2940 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 440 KB Output is correct
16 Correct 82 ms 11024 KB Output is correct
17 Incorrect 196 ms 22028 KB Tree @(100001, 3) appears more than once: for edges on positions 50000 and 149999
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 82 ms 11024 KB Output is correct
10 Correct 7 ms 1612 KB Output is correct
11 Correct 39 ms 6176 KB Output is correct
12 Correct 12 ms 2148 KB Output is correct
13 Correct 15 ms 2940 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 440 KB Output is correct
16 Correct 82 ms 11024 KB Output is correct
17 Incorrect 0 ms 204 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 2
18 Halted 0 ms 0 KB -