Submission #1171196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171196		jerzyk	Meetings (JOI19_meetings)	C++20	0 / 100	1184 ms	748 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 2'007;
bool vis[N];
int siz[N];
vector<int> ed[N];
int cen;

bool Cp(int a, int b)
{
    return (siz[a] > siz[b]);
}

void DFS(int v, int il)
{
    vis[v] = 1; siz[v] = 1;
    bool czy = 1;
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        if(vis[ed[v][i]]) continue;
        DFS(ed[v][i], il);
        if(siz[ed[v][i]] > il / 2) czy = 0;

        siz[v] += siz[ed[v][i]];
    }
    if(il - siz[v] > il / 2) czy = 0;
    if(czy) cen = v;
    vis[v] = 0;
}

void Insert(int a, int b, int c)
{
    erase(ed[a], b); erase(ed[b], a);
    ed[a].pb(c); ed[b].pb(c);
    ed[c].pb(a); ed[c].pb(b);
}

void Ins(int nw, int n)
{
    int il = n, s = 1;
    for(int i = 0; i < n; ++i) vis[i] = 0;
    while(true)
    {
        DFS(s, il);
        s = -1;
        int v = cen;
        vector<int> akt;
        for(int i = 0; i < (int)ed[v].size(); ++i)
            if(!vis[ed[v][i]]) akt.pb(ed[v][i]);
        sort(akt.begin(), akt.end(), Cp);
        vis[v] = 1;
        for(int i = 0; i < (int)akt.size(); ++i)
        {
            int a = Query(v, akt[i], nw);
            if(a == nw)
            {
                Insert(v, akt[i], nw);
                return;
            }
            if(a == akt[i])
            {
                il = siz[akt[i]];
                s = akt[i];
                break;
            }
        }
        if(s == -1)
        {
            ed[v].pb(nw);
            ed[nw].pb(v);
            return;
        }
    }
}

void Solve(int _N)
{
    int n = _N;
    if(n == 1) return;
    ed[0].pb(1); ed[1].pb(0);
    for(int i = 2; i < n; ++i)
        Ins(i, i);
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < (int)ed[i].size(); ++j)
            if(ed[i][j] > i)
                Bridge(i, ed[i][j]);
}

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