Submission #1133347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133347		adaawf	Amusement Park (JOI17_amusement_park)	C++20	10 / 100	16 ms	4680 KiB

Joi

#include <bits/stdc++.h>
#include "Joi.h"
using namespace std;
int pa[100005], s[100005], z = 0;
vector<int> g[100005], vv;
int Find(int x) {
    if (x == pa[x]) return x;
    return pa[x] = Find(pa[x]);
}
void Merge(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x == y) return;
    if (s[x] > s[y]) swap(x, y);
    pa[x] = y;
    s[y] += s[x];
}
int ma = 0, d[100005], pp[100005], dd[100005], a[100005], b[65], kk, da[100005], db[100005], zz = 0, res[100005];
void dfs(int x, int p, long long int y) {
    a[x] = 1;
    da[x] = ++zz;
    for (int w : g[x]) {
        if (w == p) continue;
        d[w] = d[x] + 1;
        pp[w] = x;
        dfs(w, x, y);
        a[x] = max(a[x], a[w] + 1);
    }
    db[x] = ++zz;
    ma = max(ma, d[x]);
}
void dfs2(int x, int p) {
    if (x) vv.push_back(x);
    for (int w : g[x]) {
        if (w == p || dd[w] == 0) continue;
        if (da[w] <= da[kk] && db[kk] <= db[w]) continue;
        dfs2(w, x);
    }
    for (int w : g[x]) {
        if (w == p || dd[w] == 0) continue;
        if (da[w] <= da[kk] && db[kk] <= db[w]) {
            dfs2(w, x);
        }
    }
    vv.push_back(x);
}
void Joi(int n, int m, int aa[], int bb[], long long int x, int t) {
    z = zz = 0;
    vv.clear();
    for (int i = 0; i < n; i++) {
        pa[i] = i; dd[i] = 0; d[i] = 0;
        s[i] = 1;
        g[i].clear();
    }
    for (int i = 0; i < m; i++) {
        if (Find(aa[i]) != Find(bb[i])) {
            Merge(aa[i], bb[i]);
            g[aa[i]].push_back(bb[i]);
            g[bb[i]].push_back(aa[i]);
        }
    }
    dfs(0, 0, x);
    if (ma >= 59) {
        for (int i = 0; i < n; i++) {
            if (x & (1ll << (d[i] % 60))) MessageBoard(i, 1);
            else MessageBoard(i, 0);
        }
    }
    else {
        int h = 0;
        vector<int> v;
        while (1) {
            v.push_back(h);
            dd[h] = 1;
            int fl = 0, k = 0;
            for (int w : g[h]) {
                if (w == pp[h]) continue;
                if (fl < a[w]) {
                    fl = a[w];
                    k = w;
                }
            }
            if (fl == 0) break;
            h = k;
        }
        queue<int> q;
        for (int w : v) q.push(w);
        while (v.size() < 60) {
            int p = q.front();
            q.pop();
            for (int w : g[p]) {
                if (dd[w] == 0) {
                    dd[w] = 1;
                    if (v.size() < 60) v.push_back(w);
                    q.push(w);
                }
            }
        }
        for (int i = 0; i < v.size(); i++) {
            if (x & (1ll << i)) MessageBoard(v[i], 1);
            else MessageBoard(v[i], 0);
        }
        for (int i = 0; i < n; i++) {
            if (dd[i] == 0) {
                MessageBoard(i, 0);
            }
        }
    }
}

Ioi

#include <bits/stdc++.h>
#include "Ioi.h"
using namespace std;
int pa[100005], s[100005], z = 0;
vector<int> g[100005], vv;
int Find(int x) {
    if (x == pa[x]) return x;
    return pa[x] = Find(pa[x]);
}
void Merge(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x == y) return;
    if (s[x] > s[y]) swap(x, y);
    pa[x] = y;
    s[y] += s[x];
}
int ma = 0, d[100005], pp[100005], dd[100005], a[100005], b[65], kk, da[100005], db[100005], zz = 0, res[100005];
void dfs(int x, int p, long long int y) {
    a[x] = 1;
    da[x] = ++zz;
    for (int w : g[x]) {
        if (w == p) continue;
        d[w] = d[x] + 1;
        pp[w] = x;
        dfs(w, x, y);
        a[x] = max(a[x], a[w] + 1);
    }
    db[x] = ++zz;
    ma = max(ma, d[x]);
}
void dfs2(int x, int p) {
    if (x) vv.push_back(x);
    for (int w : g[x]) {
        if (w == p || dd[w] == 0) continue;
        if (da[w] <= da[kk] && db[kk] <= db[w]) continue;
        dfs2(w, x);
    }
    for (int w : g[x]) {
        if (w == p || dd[w] == 0) continue;
        if (da[w] <= da[kk] && db[kk] <= db[w]) {
            dfs2(w, x);
        }
    }
    vv.push_back(x);
}
long long Ioi(int n, int m, int aa[], int bb[], int p, int v, int t) {
    z = zz = 0;
    vv.clear();
    for (int i = 0; i < n; i++) {
        pa[i] = i; dd[i] = 0; d[i] = 0;
        s[i] = 1;
        g[i].clear();
    }
    for (int i = 0; i < m; i++) {
        if (Find(aa[i]) != Find(bb[i])) {
            Merge(aa[i], bb[i]);
            g[aa[i]].push_back(bb[i]);
            g[bb[i]].push_back(aa[i]);
        }
    }
    dfs(0, 0, 0);
    long long int res = 0;
    if (ma >= 59) {
        if (d[p] >= 59) {
            if (v == 1) res += (1ll << (d[p] % 60));
            for (int i = 0; i < 59; i++) {
                int h = Move(pp[p]);
                p = pp[p];
                if (h) res += (1ll << (d[p] % 60));
            }
        }
        else {
            while (p != 0) {
                v = Move(pp[p]);
                p = pp[p];
            }
            if (v) res += 1;
            for (int i = 0; i < 59; i++) {
                int h = 0, ma = 0;
                for (int w : g[p]) {
                    if (w == pp[p]) continue;
                    if (ma < a[w]) {
                        ma = a[w];
                        h = w;
                    }
                }
                v = Move(h);
                p = h;
                if (v) res += (1ll << d[p]);
            }
        }
    }
    else {
        int h = 0;
        vector<int> va;
        while (1) {
            va.push_back(h);
            dd[h] = ++z;
            int fl = 0, k = 0;
            for (int w : g[h]) {
                if (w == pp[h]) continue;
                if (fl < a[w]) {
                    fl = a[w];
                    k = w;
                }
            }
            if (fl == 0) break;
            h = k;
        }
        kk = va.back();
        queue<int> q;
        for (int w : va) q.push(w);
        while (va.size() < 60) {
            int p = q.front();
            q.pop();
            for (int w : g[p]) {
                if (dd[w] == 0) {
                    dd[w] = ++z;
                    if (va.size() < 60) va.push_back(w);
                    q.push(w);
                }
            }
        }
        while (p != 0) {
            v = Move(pp[p]);
            p = pp[p];
        }
        if (v) b[dd[p]] = v;
        dfs2(0, 0);
        while (vv.back() != kk) vv.pop_back();
        for (int i = 0; i < vv.size(); i++) {
            v = Move(vv[i]);
            p = vv[i];
            b[dd[p]] = v;
        }
        for (int i = 0; i <= 60; i++) {
            if (b[i]) res += (1ll << (i - 1));
        }
    }
    return res;
}

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