oj.uz

답안 #470260

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
470260 2021-09-03T10:42:46 Z luciocf Amusement Park (JOI17_amusement_park) C++14
0 / 100
 3000 ms 262148 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 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]++, grau_0[w2]++;

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

        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]--, grau_0[w2]--;

        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]);

        adj_0[A[i]].insert(B[i]);
        adj_0[B[i]].insert(A[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 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] = 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]++, grau[w2]++;

        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]--, grau[w2]--;

        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]);

        adj[A[i]].insert(B[i]);
        adj[B[i]].insert(A[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:68:13: warning: 'out' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |             if (w != out)
      |             ^~

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

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 164 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4460 KB Output is correct
2 Correct 7 ms 4460 KB Output is correct
3 Correct 6 ms 4436 KB Output is correct
4 Execution timed out 3092 ms 9512 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 200 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 205 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -