oj.uz

Submission #470245

# Submission time Handle Problem Language Result Execution time Memory
470245 2021-09-03T10:25:09 Z luciocf Amusement Park (JOI17_amusement_park) C++14
0 / 100
 205 ms 262148 KB 
#include <bits/stdc++.h>
#include "Joi.h"

using namespace std;

const int maxn = 2e4+10;

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

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 != v)
            {
                out = w, bit[v] = bit[w];
                break;
            }
        }

        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 Joi(int N, int M, int A[], int B[], long long X, 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);

    for (int i = 0; i < N; i++)
    {
        if (X & (1ll<<bit[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 != v)
            {
                out = w, bit[v] = bit[w];
                break;
            }
        }

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

static 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);
    }

    if (p != -1) Move(p);
}

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[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(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:70:13: warning: 'out' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |             if (w != out)
      |             ^~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4336 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 162 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4464 KB Output is correct
2 Correct 5 ms 4336 KB Output is correct
3 Incorrect 6 ms 4592 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 205 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 203 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -