oj.uz

답안 #446389

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
446389 2021-07-21T20:26:54 Z luciocf 분수 공원 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -