oj.uz

Submission #41818

# Submission time Handle Problem Language Result Execution time Memory
41818 2018-02-21T09:29:47 Z krauch Amusement Park (JOI17_amusement_park) C++14
0 / 100
 33 ms 5384 KB 
#include "Joi.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define eb emplace_back
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)

static const int MAXN = 2e4 + 6;

static int n, m, comp[MAXN], cnt;
static ll X, sz[MAXN];
static vector < int > g[MAXN];
static bool u[MAXN];

void dfs(int v) {
    u[v] = 1;
    for (auto to : g[v]) {
        if (u[to]) continue;
        if (sz[comp[v]] == 60)
            comp[to] = ++cnt;
        else
            comp[to] = comp[v];
        MessageBoard(to - 1, (X >> sz[comp[to]]) & 1);
        sz[comp[to]]++;
        dfs(to);
    }
}

void Joi(int _n, int _m, int A[], int B[], long long _x, int _t) {
    n = _n, m = _m;
    X = _x;
    forn(i, 0, m - 1) {
        A[i]++, B[i]++;
        g[A[i]].eb(B[i]);
        g[B[i]].eb(A[i]);
    }

    cnt = 1;
    comp[1] = 1;
    sz[comp[1]] = 1;
    MessageBoard(0, X & 1);
    dfs(1);
}


#ifdef krauch
int main() {
    return 0;
}
#endif

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

using namespace std;

typedef long long ll;

#define eb emplace_back
#define sz(a) (int)a.size()
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)

static const int MAXN = 2e4 + 6;

static int n, m, comp[MAXN], cnt, par[MAXN], CUR;
static ll X, sz[MAXN], lvl[MAXN], ans[66];
static vector < int > g[MAXN];
static bool u[MAXN];

void dfs(int v) {
    CUR++;
    u[v] = 1;
    for (auto to : g[v]) {
        if (u[to]) continue;
        if (sz[comp[v]] == 60)
            comp[to] = ++cnt;
        else
            comp[to] = comp[v];
        lvl[to] = sz[comp[to]];
        sz[comp[to]]++;
        par[to] = v;
        dfs(to);
    }
}

void dfs2(int v, int val) {
    u[v] = 1;
    ans[lvl[v]] |= val;
    for (auto to : g[v]) {
        if (u[to] || comp[to] != comp[v]) continue;
        int toval = Move(to - 1);
        dfs2(to, toval);
        val = Move(v - 1);
    }
}

ll Ioi(int _n, int _m, int A[], int B[], int _p, int _v, int _t) {
    n = _n, m = _m;
    int st = _p + 1, stval = _v;
    bool ok = 0;
    forn(i, 0, m - 1) {
        //A[i]++, B[i]++;
        ok |= (A[i] == 1 || B[i] == 1);
        g[A[i]].eb(B[i]);
        g[B[i]].eb(A[i]);
    }

    assert(ok);

    cnt = 1;
    comp[1] = 1;
    sz[comp[1]] = 1;
    dfs(1);

    while (sz[comp[st]] != 60) {
        st = par[st];
        stval = Move(st - 1);
    }
    forn(i, 1, n) u[i] = 0;
    dfs2(st, stval);

    ll res = 0;
    forn(i, 0, 60) {
        res |= (ans[i] << ll(i));
    }
    return res;
}


#ifdef krauch
int main() {
    return 0;
}
#endif

Compilation message

Ioi.cpp:16:11: warning: 'X' defined but not used [-Wunused-variable]
 static ll X, sz[MAXN], lvl[MAXN], ans[66];
           ^

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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