Submission #1266890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266890		tvgk	Meetings (JOI19_meetings)	C++20	29 / 100	785 ms	984 KiB

meetings

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

int n, sz[mxN];
bool ers[mxN], vis[mxN];
set<int> w[mxN];

void Del(int u, int v)
{
    w[u].erase(v);
    w[v].erase(u);
}

void Add(int u, int v)
{
    if (u == v)
        return;

    w[u].insert(v);
    w[v].insert(u);
}

void DFS(int j, int par)
{
    sz[j] = 1;

    for (int i : w[j])
    {
        if (i == par || ers[i])
            continue;

        DFS(i, j);
        sz[j] += sz[i];
    }
}

int Find(int j, int par, int num)
{
    for (int i : w[j])
    {
        if (i == par || ers[i])
            continue;

        if (sz[i] * 2 > num)
            return Find(i, j, num);
    }
    return j;
}

void Centroid(int root, int nw)
{
    DFS(root, -1);

    if (sz[root] == 1)
    {
        Add(root, nw);
        return;
    }

    root = Find(root, -1, sz[root]);
    DFS(root, -1);

    ers[root] = 1;
    vector<ii> child;
    for (int i : w[root])
        child.push_back({sz[i], i});
    sort(child.begin(), child.end(), less<ii>());

    if (child.size() % 2)
        child.push_back({0, root});

    for (int i = 0; i < child.size(); i += 2)
    {
        int u = child[i].se;
        int v = child[i + 1].se;
        int res = Query(u, v, nw);

        if (res == root)
            continue;

        if (res == u)
        {
            Centroid(u, nw);
            return;
        }

        if (res == v)
        {
            Centroid(v, nw);
            return;
        }

        int tmp = Query(u, res, root);
        if (tmp != res)
            u = v;

        Del(u, root);
        Add(u, res);
        Add(root, res);
        Add(nw, res);

        vis[res] = 1;

        return;
    }
    Add(root, nw);
}

random_device rd;
mt19937 g(rd());

void Solve(int n)
{
    Add(0, 1);

    vector<int> stt;
    for (int i = 2; i < n; i++)
        stt.push_back(i);
    shuffle(stt.begin(), stt.end(), g);

    for (int i : stt)
    {
        if (vis[i])
            continue;

        for (int j = 0; j <= n; j++)
            ers[j] = 0;

        Centroid(0, i);
    }

    for (int i = 0; i < n; i++)
    {
        for (int j : w[i])
        {
            if (j > i)
                Bridge(i, j);
        }
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 0 / 71