oj.uz

답안 #446388

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
446388 2021-07-21T20:24:03 Z luciocf 분수 공원 (IOI21_parks) C++17
0 / 100
 0 ms 204 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};
                i++;
            }
        }

        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};
                i++;
            }
        }

        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:111:1: warning: control reaches end of non-void function [-Wreturn-type]
  111 | }
      | ^

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 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 Incorrect 0 ms 204 KB Solution announced impossible, but it is possible.
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 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 Incorrect 0 ms 204 KB Solution announced impossible, but it is possible.
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 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 Incorrect 0 ms 204 KB Solution announced impossible, but it is possible.
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 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 Incorrect 0 ms 204 KB Solution announced impossible, but it is possible.
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 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 Incorrect 0 ms 204 KB Solution announced impossible, but it is possible.
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 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 Incorrect 0 ms 204 KB Solution announced impossible, but it is possible.
5 Halted 0 ms 0 KB -