Submission #533996

#	Time	Username	Problem	Language	Result	Execution time	Memory
533996		iulia13	Meetings (JOI19_meetings)	C++14	17 / 100	495 ms	644 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
const int N = 2005;
int vc[N];
int viz[N]; ///noduri 0... n - 1
vector <int> g[N];
int nxt[N];
int prv[N];
int cod[N];
int decod[N];
int subarb[N];
int intree[N];
void dfsSize(int nod, int dad = 0)
{
    subarb[nod] = 1;
    for (auto x : g[nod])
    {
        if (viz[x] || dad == x)
            continue;
        dfsSize(x, nod);
        subarb[nod] += subarb[x];
    }
}
int centroid(int nod, int dad, int newN)
{
    for (auto x : g[nod])
    {
        if (viz[x] || dad == x)
            continue;
        if (subarb[x] > newN / 2)
            return centroid(x, nod, newN);
    }
    return nod;
}
struct ura{
    int x, sz;
} sons[20];
bool cmp(ura a, ura b)
{
    return a.sz > b.sz;
}
int nrsons;
int compute_centroid(int nod, int newN)
{
    dfsSize(nod, 0);
    int root = centroid(nod, 0, newN);
    dfsSize(root, 0);
    nrsons = 0;
    for (auto x : g[root])
        sons[++nrsons] = {x, subarb[x]};
    sort(sons + 1, sons + nrsons + 1, cmp);
    return root;
}
void rupe(int a, int b, int c)
{
    for (auto &x : g[a])
        if (x == b)
        {
            x = c;
            break;
        }
     for (auto &x : g[b])
        if (x == a)
        {
            x = c;
            break;
        }
    g[c].push_back(a);
    g[c].push_back(b);
}
/*int Query(int a, int b, int c)
{
    cout << a << " " << b << " " << c;
    cin >> a;
    return a;
}
void Bridge(int u, int v)
{
    cout << u << " " << v << endl;
}*/
void Solve(int n)
{
    int nodes = 0;
    for (int i = 0; i < n; i++)
        nxt[i] = i + 1;
    for (int i = 1; i <= n; i++)
        prv[i] = i - 1;
    for (int i = 1; i <= n && nodes < n; i++)
    {
        int j = rand() % n + 1, cnt = 0;
        while (intree[j] && cnt <= 500)
        {
            cnt++;
            j = rand() % n + 1;
        }
        if (intree[j])
            j = nxt[0];
        int p = prv[j];
        int q = nxt[j];
        intree[j] = 1;
        prv[q] = p;
        nxt[p] = q;
        for (int hh = 1; hh <= nodes; hh++)
            viz[hh] = 0;
        nodes++;
        cod[j] = nodes;
        decod[nodes] = j - 1;
        int myn = nodes;
        int mynewnod = 1;
        int nrnodes = nodes - 1;
        if (!nrnodes)
            continue;
        while(true)
        {
            auto root = compute_centroid(mynewnod, nrnodes);
            if (nrsons == 0)
            {
                g[root].push_back(myn);
                g[myn].push_back(root);
                break;
            }
            int h = 1, ok = 0;
            int nou = decod[myn];
            int realroot = decod[root];
            while (h + 1 <= nrsons && !ok)
            {
                int v1 = decod[sons[h].x];
                int v2 = decod[sons[h + 1].x];
                int ans = Query(v1, v2, nou);
                if (ans == realroot) ///not important
                    h += 2;
                else
                if (ans == v1) ///subarb v1
                {
                    ok = 2;
                    viz[root] = 1;
                    mynewnod = sons[h].x;
                    nrnodes = subarb[sons[h].x];
                }
                else
                if (ans == v2)
                {
                    ok = 2;
                    viz[root] = 1;
                    mynewnod = sons[h + 1].x;
                    nrnodes = subarb[sons[h].x];
                }
                else
                if (ans == nou)
                {
                    ok = 1;
                    if (Query(v1, realroot, nou) == nou)
                        rupe(root, sons[h].x, myn);
                    else
                        rupe(root, sons[h + 1].x, myn);
                }
                else
                {
                    ok = 1;
                    nodes++;
                    intree[ans + 1] = 1;
                    decod[nodes] = ans;
                    cod[ans] = nodes;
                    if (Query(v1, realroot, ans) == ans)
                        rupe(root, sons[h].x, nodes);
                    else
                        rupe(root, sons[h + 1].x, nodes);
                    g[nodes].push_back(myn);
                    g[myn].push_back(nodes);
                }

            }
            if (h == nrsons && !ok)
            {
                int v1 = decod[sons[h].x];
                int answ = Query(v1, realroot, nou);
                if (answ != realroot)
                {
                    if (answ == v1)
                    {
                        ok = 2;
                        mynewnod = sons[h].x;
                        viz[root] = 1;
                        nrnodes = subarb[sons[h].x];
                    }
                    else
                    if (answ == nou)
                    {
                        ok = 1;
                        rupe(root, sons[h].x, myn);
                    }
                    else
                    {
                        ok = 1;
                        nodes++;
                        intree[answ + 1] = 1;
                        decod[nodes] = answ;
                        rupe(root, sons[h].x, nodes);
                        g[nodes].push_back(myn);
                        g[myn].push_back(nodes);
                    }
                }
            }
            if (ok == 0)
            {
                ok = 1;
                g[myn].push_back(root);
                g[root].push_back(myn);
            }
            if (ok != 2)
                break;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (auto j : g[i])
        {
            if (decod[i] < decod[j])
                Bridge(decod[i], decod[j]);
        }
    }

}/*
int main()
{
    int n;
    cin >> n;
    Solve(n);
    return 0;
}
*/

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