Submission #108960

#	Time	Username	Problem	Language	Result	Execution time	Memory
108960		PeppaPig	Amusement Park (JOI17_amusement_park)	C++14	28 / 100	89 ms	24416 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;

const int N = 1e4+5;

static vector<int> g[N];
static vector<pii> init;
static int pre[N], pos[N];

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

static void gen_tree(int n, int m, int A[], int B[]) {
    int par[N]; iota(par, par+N, 0);
    vector<pii> E;
    
    function<int(int)> find = [&](int x) { return par[x] = x == par[x] ? x : find(par[x]); };

    for(int i = 0; i < m; i++) {
        if(A[i] > B[i]) swap(A[i], B[i]);
        E.emplace_back(A[i], B[i]);
    }
    sort(E.begin(), E.end());

    vector<pii> ret;
    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(int i = 0; i < n; i++) if(pre[i] < 60) pos[i] = pre[i];
    for(pii e : ret) {
        int a, b; tie(a, b) = e;
        if(pre[a] < 60 && pre[b] < 60) init.emplace_back(a, b);
    }
}

static int deg[N];
static vector<pii> t[N];

static void extend_tree(int u, int p) {
    if(pre[u] < 60) return;
    vector<pii> v = t[p];
    for(pii e : v) {
        int a, b; tie(a, b) = e;
        ++deg[a], ++deg[b];
    }
    int leaf;
    for(pii e : v) {
        int a, b; tie(a, b) = e;
        if(deg[a] > deg[b]) swap(a, b);
        if(deg[a] == 1) { leaf = a; break; }
    }
    pos[u] = pos[leaf];
    for(pii e : v) {
        int a, b; tie(a, b) = e;
        --deg[a], --deg[b];
        if(a == leaf || b == leaf) continue;
        t[u].emplace_back(a, b);
    }
    t[u].emplace_back(u, p);
    for(int v : g[u]) if(v != p) extend_tree(v, u);
}

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

    for(int i = 0; i < n; i++) if(pre[i] < 60) t[i] = init;
    for(int i = 0; i < n; i++) if(pre[i] < 60) for(int v : g[i]) extend_tree(v, i);
    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;

const int N = 1e4+5;

static vector<int> g[N];
static vector<pii> init;
static int pre[N], pos[N];

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

static void gen_tree(int n, int m, int A[], int B[]) {
    int par[N]; iota(par, par+N, 0);
    vector<pii> E;
    
    function<int(int)> find = [&](int x) { return par[x] = x == par[x] ? x : find(par[x]); };

    for(int i = 0; i < m; i++) {
        if(A[i] > B[i]) swap(A[i], B[i]);
        E.emplace_back(A[i], B[i]);
    }
    sort(E.begin(), E.end());

    vector<pii> ret;
    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(int i = 0; i < n; i++) if(pre[i] < 60) pos[i] = pre[i];
    for(pii e : ret) {
        int a, b; tie(a, b) = e;
        if(pre[a] < 60 && pre[b] < 60) init.emplace_back(a, b);
    }
}

static int deg[N];
static vector<pii> t[N];

static void extend_tree(int u, int p) {
    if(pre[u] < 60) return;
    vector<pii> v = t[p];
    for(pii e : v) {
        int a, b; tie(a, b) = e;
        ++deg[a], ++deg[b];
    }
    int leaf;
    for(pii e : v) {
        int a, b; tie(a, b) = e;
        if(deg[a] > deg[b]) swap(a, b);
        if(deg[a] == 1) { leaf = a; break; }
    }
    pos[u] = pos[leaf];
    for(pii e : v) {
        int a, b; tie(a, b) = e;
        --deg[a], --deg[b];
        if(a == leaf || b == leaf) continue;
        t[u].emplace_back(a, b);
    }
    t[u].emplace_back(u, p);
    for(int v : g[u]) if(v != p) extend_tree(v, u);
}

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) {
    gen_tree(n, m, A, B);

    for(int i = 0; i < n; i++) if(pre[i] < 60) t[i] = init;
    for(int i = 0; i < n; i++) if(pre[i] < 60) for(int v : g[i]) extend_tree(v, i);
    for(int i = 0; i < n; i++) g[i].clear();

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

    return ans;
}

Compilation message (stderr)

Joi.cpp: In function 'void extend_tree(int, int)':
Joi.cpp:68: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:68:22: warning: 'leaf' may be used uninitialized in this function [-Wmaybe-uninitialized]
     pos[u] = pos[leaf];
              ~~~~~~~~^

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