oj.uz

Submission #46661

# Submission time Handle Problem Language Result Execution time Memory
46661 2018-04-22T13:54:10 Z teomrn Amusement Park (JOI17_amusement_park) C++14
0 / 100
 45 ms 10656 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;
    }
}

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

set <int> nr;

static void mk_cols(int nod)
{
    assert(nr.find(nod) == nr.end());
    nr.insert(nod);
    for (int i(0); i < adia[nod].size(); i++) {
        if (adia[nod][i] == tata[nod]) {
            swap(adia[nod][i], adia[nod].back());
            adia[nod].pop_back();
            i--;
        }
    }
    col[nod] = colact;
    colact = (colact + 1) % nrcol;

    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;
        int q = adia[nod][i];
        int z = tata[q];
        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(0);
}

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

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


static void mk_cols(int nod)
{
    for (int i(0); i < adia[nod].size(); i++) {
        if (adia[nod][i] == tata[nod]) {
            swap(adia[nod][i], adia[nod].back());
            adia[nod].pop_back();
            i--;
        }
    }
    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(0);
    tata[0] = -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()]]) {
        assert(tata[nod] != -1);
        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:48:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i(0); i < adia[nod].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~~
Joi.cpp:60:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i(0); i < adia[nod].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~~
Joi.cpp:64:13: warning: unused variable 'z' [-Wunused-variable]
         int z = tata[q];
             ^
Joi.cpp: At global scope:
Joi.cpp:40:12: warning: 'viz' defined but not used [-Wunused-variable]
 static int viz[100010];
            ^~~
Joi.cpp:35:12: warning: 'fii' defined but not used [-Wunused-variable]
 static int fii[100010];
            ^~~

Ioi.cpp: In function 'void mk_cols(int)':
Ioi.cpp:45:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i(0); i < adia[nod].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~~
Ioi.cpp:55:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i(0); i < adia[nod].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~~
Ioi.cpp: At global scope:
Ioi.cpp:35:12: warning: 'fii' defined but not used [-Wunused-variable]
 static int fii[100010];
            ^~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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