oj.uz

답안 #470273

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
470273 2021-09-03T11:09:41 Z luciocf Amusement Park (JOI17_amusement_park) C++14
0 / 100
 1340 ms 15600 KB 
#include <bits/stdc++.h>
#include "Joi.h"

using namespace std;

const int maxn_0 = 2e4+10;

static int grau_0[maxn_0], bit_0[maxn_0];

static vector<int> grafo_0[maxn_0], grupo_0[maxn_0];

static set<int> adj_0[maxn_0];

static int pai_0[maxn_0];
static bool mark_0[maxn_0];

void get_sp_0(int u)
{
    mark_0[u] = 1;

    for (auto v: grafo_0[u])
    {
        if (!mark_0[v])
        {
            pai_0[v] = u;
            get_sp_0(v);
        }
    }
}

static bool connect_0(int u, int v)
{
    return (adj_0[u].find(v) != adj_0[u].end());
}

static void dfs_0_0(int u, int p)
{
    if (grupo_0[0].size() < 60)
    {
        bit_0[u] = grupo_0[0].size();
        grupo_0[0].push_back(u);
    }

    for (auto v: grafo_0[u])
        if (v != p)
            dfs_0_0(v, u);
}

static void dfs_1(int u, int p)
{
    for (auto v: grafo_0[u])
    {
        if (v == p) continue;

        bool ok = 0;
        for (auto w: grupo_0[u])
            if (w == v)
                ok = 1;

        if (ok)
        {
            for (auto w: grupo_0[u])
                grupo_0[v].push_back(w);

            dfs_1(v, u);
            continue;
        }

        for (auto w1: grupo_0[u])
            for (auto w2: grupo_0[u])
                if (w1 != w2 && connect_0(w1, w2))
                    grau_0[w1]++;

        int out;
        for (auto w: grupo_0[u])
        {
            if (grau_0[w] == 1 && w != u)
            {
                out = w, bit_0[v] = bit_0[w];
                break;
            }
        }

        grupo_0[v].push_back(v);
        for (auto w: grupo_0[u])
            if (w != out)
                grupo_0[v].push_back(w);

        for (auto w1: grupo_0[u])
            for (auto w2: grupo_0[u])
                if (w1 != w2 && connect_0(w1, w2))
                    grau_0[w1]--;

        dfs_1(v, u);
    }  
}

void Joi(int N, int M, int A[], int B[], long long X, int T)
{
    for (int i = 0; i < M; i++)
    {
        grafo_0[A[i]].push_back(B[i]);
        grafo_0[B[i]].push_back(A[i]);
    }

    get_sp_0(0);

    for (int i = 0; i < N; i++)
        grafo_0[i].clear();

    for (int i = 1; i < N; i++)
    {
        grafo_0[i].push_back(pai_0[i]);
        grafo_0[pai_0[i]].push_back(i);

        adj_0[i].insert(pai_0[i]);
        adj_0[pai_0[i]].insert(i);
    }

    dfs_0_0(0, -1);
    dfs_1(0, -1);

    for (int i = 0; i < N; i++)
    {
        if (X & (1ll<<bit_0[i])) MessageBoard(i, 1);
        else MessageBoard(i, 0);
    }
}

#include <bits/stdc++.h>
#include "Ioi.h"

using namespace std;

const int maxn = 2e4+10;

static int grau[maxn], bit[maxn];

static bool on[61];

static vector<int> grafo[maxn], grupo[maxn];

static set<int> adj[maxn];

static int pai[maxn];
static bool mark[maxn];

void get_sp(int u)
{
    mark[u] = 1;

    for (auto v: grafo[u])
    {
        if (!mark[v])
        {
            pai[v] = u;
            get_sp(v);
        }
    }
}

static bool connect(int u, int v)
{
    return (adj[u].find(v) != adj[u].end());
}

static void dfs_0(int u, int p)
{
    if (grupo[0].size() < 60)
    {
        bit[u] = (int)grupo[0].size();
        grupo[0].push_back(u);
    }

    for (auto v: grafo[u])
        if (v != p)
            dfs_0(v, u);
}

static void dfs(int u, int p)
{
    for (auto v: grafo[u])
    {
        if (v == p) continue;

        bool ok = 0;
        for (auto w: grupo[u])
            if (w == v)
                ok = 1;

        if (ok)
        {
            for (auto w: grupo[u])
                grupo[v].push_back(w);

            dfs(v, u);
            continue;
        }

        for (auto w1: grupo[u])
            for (auto w2: grupo[u])
                if (w1 != w2 && connect(w1, w2))
                    grau[w1]++;

        int out;
        for (auto w: grupo[u])
        {
            if (grau[w] == 1 && w != u)
            {
                out = w, bit[v] = bit[w];
                break;
            }
        }

        grupo[v].push_back(v);
        for (auto w: grupo[u])
            if (w != out)
                grupo[v].push_back(w);

        for (auto w1: grupo[u])
            for (auto w2: grupo[u])
                if (w1 != w2 && connect(w1, w2))
                    grau[w1]--;

        dfs(v, u);
    }  
}

void get(int u, int p)
{
    for (auto v: grafo[u])
    {
        if (v == p) continue;

        bool ok = 0;
        for (auto w: grupo[u])
            if (v == w)
                ok = 1;

        if (!ok) continue;

        on[v] = Move(v);
        get(v, u);
        Move(u);
    }
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T)
{
    for (int i = 0; i < M; i++)
    {
        grafo[A[i]].push_back(B[i]);
        grafo[B[i]].push_back(A[i]);
    }

    get_sp(0);

    for (int i = 0; i < N; i++)
        grafo[i].clear();

    for (int i = 1; i < N; i++)
    {
        grafo[i].push_back(pai[i]);
        grafo[pai[i]].push_back(i);

        adj[i].insert(pai[i]);
        adj[pai[i]].insert(i);
    }

    dfs_0(0, -1);
    dfs(0, -1);

    on[bit[P]] = V;
    get(P, -1);

    long long ans = 0;
    for (int i = 0; i < 60; i++)
        if (on[i])
            ans += (1ll<<i);

    return ans;
}

Compilation message

Joi.cpp: In function 'void dfs_1(int, int)':
Joi.cpp:86:13: warning: 'out' may be used uninitialized in this function [-Wmaybe-uninitialized]
   86 |             if (w != out)
      |             ^~

Ioi.cpp: In function 'void dfs(int, int)':
Ioi.cpp:88:13: warning: 'out' may be used uninitialized in this function [-Wmaybe-uninitialized]
   88 |             if (w != out)
      |             ^~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 4340 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1329 ms 15372 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4588 KB Output is correct
2 Correct 4 ms 4588 KB Output is correct
3 Correct 5 ms 4588 KB Output is correct
4 Correct 87 ms 6060 KB Output is correct
5 Incorrect 82 ms 6208 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1328 ms 15600 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1340 ms 15464 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -