Submission #1171314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171314		jerzyk	Meetings (JOI19_meetings)	C++20	29 / 100	378 ms	840 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], czyw[N];
int siz[N];
vector<int> ed[N];
int cen;

bool Cp(int a, int b)
{
    return (siz[a] > siz[b] || (siz[a] == siz[b] && a > 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(b); ed[c].pb(a); 
}

void Ins(int nw, int n)
{
    if(czyw[nw]) return;
    int il = 0, s = 0;
    for(int i = 0; i < n; ++i)
    {
        if(czyw[i]) ++il;
        vis[i] = 0;
    }
    //cerr << "Ins: " << nw << "\n";
    czyw[nw] = 1;
    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]);
        for(int i = 0; i < (int)akt.size(); ++i)
            if(siz[akt[i]] > siz[v])
                siz[akt[i]] = il - siz[v];
        sort(akt.begin(), akt.end(), Cp);
        vis[v] = 1;
        //bool xd = 0;
        for(int i = 0; i < (int)akt.size(); ++i)
        {
            int a = Query(v, akt[i], nw);
            if(a == v) continue;
            if(a == nw)
            {
                //cerr << "A: " << v << " " << akt[i] << "\n";
                Insert(v, akt[i], nw);
                //if(xd)
                    //{ed[v].pop_back(); ed[nw].pop_back();}
                //cerr << ed[akt[i]].size() << " " << ed[akt[i]][0] << "\n";
                return;
            }
            if(a == akt[i])
            {
                //cerr << "B: " << v << " " << akt[i] << "\n";
                il = siz[akt[i]];
                s = akt[i];
                break;
            }
            //if(czyw[a]) continue;
            //cerr << "C: " << v << " " << a << " " << akt[i] << " " << nw << "\n";
            erase(ed[akt[i]], v); erase(ed[v], akt[i]);
            ed[v].pb(a); ed[a].pb(v);
            ed[a].pb(nw); ed[nw].pb(a);
            ed[a].pb(akt[i]); ed[akt[i]].pb(a);
            czyw[a] = 1;
            return;
        }
        if(s == -1)
        {
            //cerr << "D: " << v << " " << akt.size() << " " << ed[v].size() << "\n";
            ed[v].pb(nw);
            ed[nw].pb(v);
            return;
        }
    }
}

void Solve(int _N)
{
    mt19937 rng(0);
    int n = _N;
    vector<int> tv;
    for(int i = 2; i < n; ++i) tv.pb(i);
    //shuffle(tv.begin(), tv.end(), rng);
    czyw[0] = 1; czyw[1] = 1;
    if(n == 1) return;
    ed[0].pb(1); ed[1].pb(0);
    for(int i = 0; i < n - 2; ++i)
        Ins(tv[i], n);

    /*for(int i = 0; i < n; ++i)
        for(int j = 0; j < (int)ed[i].size(); ++j)
            if(ed[i][j] > i)
                cerr << "Ans: " << i << " " << ed[i][j] << "\n";*/

    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: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 0 / 71