Submission #1275383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275383		tvgk	Amusement Park (JOI17_amusement_park)	C++20	0 / 100	25 ms	2668 KiB

Joi

#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define ll long long
#define fi first
#define se second
#define ii pair<ll, ll>
const int mxN = 1e5 + 7;

static int dsu[mxN], h[mxN];
static bool vis[mxN];
static vector<int> w[mxN], vc[mxN], Board[mxN];

static int Find(int j)
{
    if (dsu[j] == j)
        return j;
    else
        return dsu[j] = Find(dsu[j]);
}

static bool Union(int u, int v)
{
    u = Find(u);
    v = Find(v);

    if (u == v)
        return 0;

    dsu[v] = u;
    return 1;
}

static void Merge(int u, int v)
{
    if (vc[u].size() > vc[v].size())
        swap(vc[u], vc[v]);

    for (int i : vc[u])
        vc[v].push_back(i);
    vc[u].clear();
}

static int lst = -1;
static void DFS(int j)
{
    vc[j].push_back(j);
    for (int i : w[j])
    {
        if (vc[i].size())
            continue;

        DFS(i);
        if (lst != i)
            Merge(i, j);
    }

    if (vc[j].size() >= 60)
        lst = j;
}

static void Prepare(int j, int id, int tmp)
{
    h[j] = tmp;
    for (int i : w[j])
    {
        if (!vis[i] || h[i])
            continue;

        Prepare(i, id, tmp + 1);
        h[j] = max(h[j], h[i]);
    }
}

static bool cmp(int u, int v)
{
    return h[u] > h[v];
}

static void Build(int j, int id)
{
    if (Board[id].size() <= 60)
        Board[id].push_back(j);
    else
        MessageBoard(j, 0);
    vis[j] = 0;

    sort(w[j].begin(), w[j].end(), cmp);
    for (int i : w[j])
    {
        if (!vis[i])
            continue;

        Build(i, id);
    }
}

void Joi(int n, int m, int a[], int b[], long long x, int t)
{
    for (int i = 0; i < n; i++)
        dsu[i] = i;

    for (int i = 0; i < m; i++)
    {
        if (Union(a[i], b[i]))
        {
            w[a[i]].push_back(b[i]);
            w[b[i]].push_back(a[i]);
        }
    }

    DFS(0);

    if (lst)
        Merge(0, lst);

    for (int i = 0; i < n; i++)
    {
        if (vc[i].empty())
            continue;

        for (int j : vc[i])
            vis[j] = 1;
        Prepare(i, i, 1);
        Build(i, i);

        for (int j = 0; j < Board[i].size(); j++)
            MessageBoard(Board[i][j], (x >> j) & 1);
    }
}

Ioi

#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define ll long long
#define fi first
#define se second
#define ii pair<ll, ll>
const int mxN = 1e5 + 7;

int dsu[mxN], h[mxN], trace[mxN], mn[mxN], vis[mxN];
bool bit[mxN];
vector<int> w[mxN], vc[mxN], Board;

int Find(int j)
{
    if (dsu[j] == j)
        return j;
    else
        return dsu[j] = Find(dsu[j]);
}

bool Union(int u, int v)
{
    u = Find(u);
    v = Find(v);

    if (u == v)
        return 0;

    dsu[v] = u;
    return 1;
}

void Merge(int u, int v)
{
    if (vc[u].size() > vc[v].size())
        swap(vc[u], vc[v]);

    for (int i : vc[u])
        vc[v].push_back(i);
    vc[u].clear();
}

int lst = -1;
void DFS(int j)
{
    vc[j].push_back(j);
    for (int i : w[j])
    {
        if (vc[i].size())
            continue;

        DFS(i);
        if (lst != i)
            Merge(i, j);
    }

    if (vc[j].size() >= 60)
        lst = j;
}

void Prepare(int j, int tmp)
{
    h[j] = tmp;
    vis[j]--;
    for (int i : w[j])
    {
        if (vis[i] != 2)
            continue;

        Prepare(i, tmp + 1);
        h[j] = max(h[j], h[i]);
    }
}

bool cmp(int u, int v)
{
    return h[u] > h[v];
}

void Build(int j)
{
    if (Board.size() <= 60)
        Board.push_back(j);
    vis[j] = 0;

    sort(w[j].begin(), w[j].end(), cmp);
    for (int i : w[j])
    {
        if (!vis[i])
            continue;

        Build(i);
    }
}

void BFS(int j)
{
    queue<int> q;
    q.push(j);
    mn[j] = 0;
    while (q.size())
    {
        int j = q.front();
        q.pop();

        for (int i : w[j])
        {
            if (mn[i] > mn[j] + 1)
            {
                mn[i] = mn[j] + 1;
                q.push(i);
                trace[i] = j;
            }
        }
    }
}

int Walk(int j)
{
    if (j == -1)
        return -1;

    if (Walk(trace[j]) >= 0)
        return Move(j);
    return 0;
}

bool cmpp(int u, int v)
{
    return h[u] < h[v];
}

int cnt;
void Solve(int j)
{
    sort(w[j].begin(), w[j].end(), cmpp);
    cnt++;
    vis[j] = 0;

    for (int i : w[j])
    {
        if (!vis[i])
            continue;

        bit[i] = Move(i);
        Solve(i);
        if (cnt < 60)
            Move(j);
    }
}

ll Ioi(int n, int m, int a[], int b[], int stt, int v, int t)
{
    for (int i = 0; i < n; i++)
        dsu[i] = i;

    for (int i = 0; i < m; i++)
    {
        if (Union(a[i], b[i]))
        {
            w[a[i]].push_back(b[i]);
            w[b[i]].push_back(a[i]);
        }
    }

    DFS(0);
    if (lst)
        Merge(0, lst);

    int root = 0;
    for (int i = 0; i < n; i++)
    {
        trace[i] = -1;
        mn[i] = 1e9;
        for (int j : vc[i])
        {
            if (j == stt)
                root = i;
        }
    }

    for (int i : vc[root])
        vis[i] = 2;
    Prepare(root, 1);
    Build(root);

    BFS(stt);
    for (int i : Board)
    {
        vis[i] = 2;
        if (mn[i] < mn[root])
            root = i;
    }

    if (stt != root)
        v = Walk(root);
    bit[root] = v;

    Prepare(root, 1);
    Solve(root);

    ll ans = 0;
    for (int i = 0; i < 60; i++)
        ans += (bit[i] << i);
    return ans;
}

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