제출 #1190914

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190914		Ghulam_Junaid	Meetings (JOI19_meetings)	C++20	100 / 100	981 ms	904 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MXN = 2005;
int n, root;
vector<int> subt[MXN];
set<int> st;

bool cmp(int u, int v){
    return (Query(root, u, v) == u);
}

void get(int v){
    int u = subt[v][rng() % subt[v].size()];
    vector<int> path, cur_subt = subt[v];
    subt[v].clear();
    st.erase(v);
    
    for (int x : cur_subt){
        if (x == u) continue;
        int cen = Query(u, x, v);

        if (cen == x)
            path.push_back(x);
        else{
            subt[cen].push_back(x);
            st.insert(cen);
        }
    }

    root = v;
    sort(path.begin(), path.end(), cmp);
    path.push_back(u);
    
    for (int i = 0; i < path.size(); i ++){
        if (root < path[i]) Bridge(root, path[i]);
        else Bridge(path[i], root);
        root = path[i];
    }
}

void Solve(int nn) {
    srand(time(0));
    n = nn;
    for (int i = 1; i < n; i ++)
        subt[0].push_back(i);
    st.insert(0);

    while (!st.empty()){
        int v = *st.begin();
        get(v);
    }
}

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