oj.uz

Submission #46632

# Submission time Handle Problem Language Result Execution time Memory
46632 2018-04-22T12:17:04 Z teomrn Amusement Park (JOI17_amusement_park) C++14
0 / 100
 33 ms 10344 KB 
#include <bits/stdc++.h>
using namespace std;

#include "Joi.h"

namespace UF1 {
    int tata[100010];
    int g[100010];
    int find(int x) {
        if (tata[tata[x]] != tata[x])
            tata[x] = find(tata[x]);
        return tata[x];
    }
    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return false;

        if (g[a] > g[b])
            g[a] += g[b], tata[b] = a;
        else
            g[b] += g[a], tata[a] = b;
        return true;
    }
    void init() {
        for (int i(0); i <= 100000; i++)
            tata[i] = i, g[i] = 1;
    }
}

int col[100010], colact;
vector <int> adia[100010];
int poz_in_adia[100010];
int fii[100010];
int tata[100010];
int nrcol = 7;
int biti[64];
int unknown;
bool tells;
int viz[100010];

static void mk_cols(int nod)
{
    if (tata[nod])
        adia[nod].erase(find(adia[nod].begin(), adia[nod].end(), tata[nod]));
    col[nod] = colact;
    colact = (colact + 1) % nrcol;

    if (tells)
        MessageBoard(nod, biti[col[nod]]);

    for (int i(0); i < adia[nod].size(); i++) {
        poz_in_adia[adia[nod][i]] = i;
        tata[adia[nod][i]] = nod;
        mk_cols(adia[nod][i]);
    }
}
static void proc_input(int n, int m, int * a, int * b, long long x)
{
    UF1::init();
    for (int i(0); i < m; i++) {
        if (UF1::unite(a[i], b[i])) {
            adia[a[i]].push_back(b[i]);
            adia[b[i]].push_back(a[i]);
        }
    }
    if (x != -1) {
        for (int i(0); i < nrcol; i++) {
            biti[i] = x & 1ll;
            x >>= 1;
        }
    }
    else {
        unknown = nrcol;
        for (int i(0); i < nrcol; i++)
            biti[i] = -1;
    }
    mk_cols(1);
}
static void add_bit(int col, int bit)
{
    if (biti[col] == -1)
        unknown--;
    biti[col] = bit;
}

void Joi(int N, int M, int A[], int B[], long long X, int T)
{
    tells = 1;
    proc_input(N, M, A, B, X);
}

#include <bits/stdc++.h>
using namespace std;

#include "Ioi.h"

namespace UF {
    int tata[100010];
    int g[100010];
    int find(int x) {
        if (tata[tata[x]] != tata[x])
            tata[x] = find(tata[x]);
        return tata[x];
    }
    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return false;

        if (g[a] > g[b])
            g[a] += g[b], tata[b] = a;
        else
            g[b] += g[a], tata[a] = b;
        return true;
    }
    void init() {
        for (int i(0); i <= 100000; i++)
            tata[i] = i, g[i] = 1;
    }
}

int col[100010], colact;
vector <int> adia[100010];
int poz_in_adia[100010];
int fii[100010];
int tata[100010];
int nrcol = 7;
int biti[64];
int unknown;
bool tells;
int viz[100010];

static void mk_cols(int nod)
{
    if (tata[nod])
        adia[nod].erase(find(adia[nod].begin(), adia[nod].end(), tata[nod]));
    col[nod] = colact;
    colact = (colact + 1) % nrcol;

    for (int i(0); i < adia[nod].size(); i++) {
        poz_in_adia[adia[nod][i]] = i;
        tata[adia[nod][i]] = nod;
        mk_cols(adia[nod][i]);
    }
}
static void proc_input(int n, int m, int * a, int * b, long long x)
{
    UF::init();
    for (int i(0); i < m; i++) {
        if (UF::unite(a[i], b[i])) {
            adia[a[i]].push_back(b[i]);
            adia[b[i]].push_back(a[i]);
        }
    }
    if (x != -1) {
        for (int i(0); i < nrcol; i++) {
            biti[i] = x & 1ll;
            x >>= 1;
        }
    }
    else {
        unknown = nrcol;
        for (int i(0); i < nrcol; i++)
            biti[i] = -1;
    }
    mk_cols(1);
}
static void add_bit(int col, int bit)
{
    if (biti[col] == -1)
        unknown--;
    biti[col] = bit;
}
static void dfs(int nod, int i, int c)
{
    add_bit(col[nod], c);
    if (!unknown)
        return;
    viz[nod] = 1;

    if (adia[nod].empty() || viz[adia[nod][i % adia[nod].size()]]) {
        int x = Move(tata[nod]);
        dfs(tata[nod], poz_in_adia[nod] + 1, x);
    }
    else {
        i %= adia[nod].size();
        int x = Move(adia[nod][i]);
        dfs(adia[nod][i], 0, x);
    }
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T)
{
    proc_input(N, M, A, B, -1);
    dfs(P, 0, V);

    long long x(0);
    for (int i(0); i < nrcol; i++)
        x += biti[i] << i;
    return x;
}

Compilation message

Joi.cpp: In function 'void mk_cols(int)':
Joi.cpp:53:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i(0); i < adia[nod].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~~
Joi.cpp: At global scope:
Joi.cpp:81:13: warning: 'void add_bit(int, int)' defined but not used [-Wunused-function]
 static void add_bit(int col, int bit)
             ^~~~~~~

Ioi.cpp: In function 'void mk_cols(int)':
Ioi.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i(0); i < adia[nod].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 6896 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 9064 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 10344 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -