제출 #369808

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
369808		CodePlatina	Meetings (JOI19_meetings)	C++14	100 / 100	1289 ms	1260 KiB

meetings

#include "meetings.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <unordered_set>
//#define DEBUG

using namespace std;

unordered_set<int> gph[2020];
bool chc[2020];
int sz[2020];
bool rchc[2020];

int cen(int x, int p, int s)
{
    for(auto y : gph[x]) if(y != p && !chc[y] && sz[y] > s) return cen(y, x, s);
    return x;
}

void dfs(int x, int p)
{
    sz[x] = 1;
    for(auto y : gph[x]) if(y != p && !chc[y])
    {
        dfs(y, x);
        sz[x] += sz[y];
    }
}

void Solve(int N)
{
    for(int i = 1; i < N; ++i) if(!rchc[i])
    {
        rchc[i] = true;
        for(int j = 0; j < N; ++j) chc[j] = false;

        int pr = 0;
        while(1)
        {

            dfs(pr, -1);
            int r = cen(pr, -1, sz[pr] / 2);
            dfs(r, -1);
            chc[r] = true;

            #ifdef DEBUG
                cout << endl;
                cout << "i r" << endl;
                cout << i << ' ' << r << endl;
                cout << endl;
            #endif

            vector<int> chd;
            for(auto j : gph[r]) if(!chc[j]) chd.push_back(j);
            sort(chd.begin(), chd.end(), [](int x, int y){ return sz[x] > sz[y]; });

            bool flag = true;
            for(auto c : chd)
            {
                int t = Query(r, c, i);
                if(t != r)
                {
                    if(t != c)
                    {
                        if(t != i)
                        {
                            rchc[t] = true;
                            gph[r].erase(c);
                            gph[c].erase(r);
                            gph[r].insert(t);
                            gph[t].insert(r);
                            gph[c].insert(t);
                            gph[t].insert(c);
                            gph[i].insert(t);
                            gph[t].insert(i);
                            goto A;
                        }
                        gph[r].erase(c);
                        gph[c].erase(r);
                        gph[r].insert(i);
                        gph[i].insert(r);
                        gph[c].insert(i);
                        gph[i].insert(c);
                        goto A;
                    }
                    pr = c;
                    flag = false;
                    break;
                }
            }

            if(flag)
            {
                gph[r].insert(i);
                gph[i].insert(r);
                goto A;
            }
        }
        A:;

        #ifdef DEBUG
            cout << endl;
            cout << "gph" << endl;
            for(int i = 0; i < N; ++i) for(auto j : gph[i]) if(j > i) cout << i << ' ' << j << endl;
            cout << endl;
        #endif
    }

    for(int i = 0; i < N; ++i) for(auto j : gph[i]) if(j > i) Bridge(i, j);
}

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