Submission #108975

#	Time	Username	Problem	Language	Result	Execution time	Memory
108975		PeppaPig	Amusement Park (JOI17_amusement_park)	C++14	20 / 100	86 ms	24608 KiB

Joi

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

#define long long long
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

static const int N = 1e4+5;

static int par[N];

static int find(int x) { return par[x] = x == par[x] ? x : find(par[x]); }

static vector<pii> t[N];
static vector<int> g[N];
static int idx, pre[N], pos[N], deg[N];

static void dfs(int u, int p) {
    pre[u] = idx++;
    for(int v : g[u]) if(v != p) dfs(v, u);
}

static void extend_tree(int u, int p) {
    if(pre[u] < 60) return;
    int leaf;
    vector<pii> tree = t[p];

    for(pii e : tree) ++deg[e.x], ++deg[e.y];
    for(pii e : tree) {
        int a, b; tie(a, b) = e;
        if(deg[a] == 1 || deg[b] == 1) {
            leaf = deg[a] == 1 ? a : b;
            break;
        }
    }
    pos[u] = pos[leaf];
    for(pii e : tree) {
        --deg[e.x], --deg[e.y];
        if(e.x == leaf || e.y == leaf) continue;
        t[u].emplace_back(e);
    }
    t[u].emplace_back(u, p);
    for(int v : g[u]) if(v != p) extend_tree(v, u);
}

static void solve(int n, int m, int A[], int B[]) {
    iota(par, par+N, 0);
    vector<pii> E, ret, init;

    for(int i = 0; i < m; i++) E.emplace_back(A[i], B[i]);
    sort(E.begin(), E.end());
    for(pii e : E) {
        int a, b; tie(a, b) = e;
        if(find(a) != find(b)) {
            par[find(a)] = find(b);
            g[a].emplace_back(b), g[b].emplace_back(a);
            ret.emplace_back(a, b);
        }
    }
    dfs(0, 0);
    for(pii e : ret) if(pre[e.x] < 60 && pre[e.y] < 60) init.emplace_back(e);
    for(int i = 0; i < n; i++) if(pre[i] < 60) {
        pos[i] = pre[i];
        t[i] = init;
    }
    for(int i = 0; i < n; i++) if(pre[i] < 60) for(int v : g[i]) extend_tree(v, i);
}

void Joi(int n, int m, int A[], int B[], long X, int T) {
    solve(n, m, A, B);

    for(int i = 0; i < n; i++) MessageBoard(i, X >> pos[i] & 1);
}

Ioi

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

#define long long long
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

static const int N = 1e4+5;

static int par[N];

static int find(int x) { return par[x] = x == par[x] ? x : find(par[x]); }

static vector<pii> t[N];
static vector<int> g[N];
static int idx, pre[N], pos[N], deg[N];

static void dfs(int u, int p) {
    pre[u] = idx++;
    for(int v : g[u]) if(v != p) dfs(v, u);
}

static void extend_tree(int u, int p) {
    if(pre[u] < 60) return;
    int leaf;
    vector<pii> tree = t[p];

    for(pii e : tree) ++deg[e.x], ++deg[e.y];
    for(pii e : tree) {
        int a, b; tie(a, b) = e;
        if(deg[a] == 1 || deg[b] == 1) {
            leaf = deg[a] == 1 ? a : b;
            break;
        }
    }
    pos[u] = pos[leaf];
    for(pii e : tree) {
        --deg[e.x], --deg[e.y];
        if(e.x == leaf || e.y == leaf) continue;
        t[u].emplace_back(e);
    }
    t[u].emplace_back(u, p);
    for(int v : g[u]) if(v != p) extend_tree(v, u);
}

static void solve(int n, int m, int A[], int B[]) {
    iota(par, par+N, 0);
    vector<pii> E, ret, init;

    for(int i = 0; i < m; i++) E.emplace_back(A[i], B[i]);
    sort(E.begin(), E.end());
    for(pii e : E) {
        int a, b; tie(a, b) = e;
        if(find(a) != find(b)) {
            par[find(a)] = find(b);
            g[a].emplace_back(b), g[b].emplace_back(a);
            ret.emplace_back(a, b);
        }
    }
    dfs(0, 0);
    for(pii e : ret) if(pre[e.x] < 60 && pre[e.y] < 60) init.emplace_back(e);
    for(int i = 0; i < n; i++) if(pre[i] < 60) {
        pos[i] = pre[i];
        t[i] = init;
    }
    for(int i = 0; i < n; i++) if(pre[i] < 60) for(int v : g[i]) extend_tree(v, i);
}

static long ans;

static void get_ans(int u, int p) {
    for(int v : g[u]) if(v != p) {
        int nex = Move(v);
        if(nex) ans += 1ll << pos[v];
        get_ans(v, u);
        Move(u);
    }
}

long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
    solve(n, m, A, B);

    for(int i = 0; i < n; i++) g[i].clear();
    for(pii e : t[P]) g[e.x].emplace_back(e.y), g[e.y].emplace_back(e.x);
    if(V) ans += 1ll << pos[P];
    get_ans(P, P);

    return ans;
}

Compilation message (stderr)

Joi.cpp: In function 'void extend_tree(int, int)':
Joi.cpp:39:22: warning: 'leaf' may be used uninitialized in this function [-Wmaybe-uninitialized]
     pos[u] = pos[leaf];
              ~~~~~~~~^

Ioi.cpp: In function 'void extend_tree(int, int)':
Ioi.cpp:39:22: warning: 'leaf' may be used uninitialized in this function [-Wmaybe-uninitialized]
     pos[u] = pos[leaf];
              ~~~~~~~~^

• Subtask 1: 0 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 55
• Subtask 5: 0 / 17