Submission #1188949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188949		onbert	Meetings (JOI19_meetings)	C++20	0 / 100	1 ms	576 KiB

meetings

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

const int maxn = 2005;
int n;
vector<int> adj[maxn];
vector<int> added;
bool exist[maxn];

int sub[maxn], fa[maxn];
void dfs(int u) {
    sub[u] = 1;
    for (int v:adj[u]) if (exist[v] && v != fa[u]) {
        fa[v] = u;
        dfs(v);
        sub[u] += sub[v];
    }
}

int cent, P1, P2, cur = 0;
int mark[maxn];
void dfs2(int u) {
    if (cur == P1) cur += 1;
    else if (cur == P2) cur += 2;
    mark[u] = cur;
    for (int v:adj[u]) if (exist[v] && v != fa[u]) {
        fa[v] = u;
        dfs2(v);
    }
    if (cur == P1) cur -= 1;
    else if (cur == P2) cur -= 2;
}

void solve(int add, vector<int> vec) {
    int sz = vec.size();
    if (sz == 2) {
        int ret = Query(vec[0], vec[1], add);
        if (ret == vec[0] || ret == vec[1]) {
            adj[ret].push_back(add); adj[add].push_back(ret);
        } else {
            for (int &v:adj[vec[0]]) if (v == vec[1]) v = ret;
            for (int &v:adj[vec[1]]) if (v == vec[0]) v = ret;
            adj[ret].push_back(vec[0]); adj[ret].push_back(vec[1]);
            if (ret != add) {
                adj[ret].push_back(add);
                adj[add].push_back(ret);
                added.push_back(ret);
            }
        }
        return;
    } else if (sz == 1) {
        adj[vec[0]].push_back(add); adj[add].push_back(vec[0]);
        return;
    }

    int RT = vec[0];
    fa[RT] = -1;
    dfs(RT);
    for (int u:vec) {
        vector<pair<int,int>> child;
        if (u != RT) child.push_back({sz - sub[u], fa[u]});
        for (int v:adj[u]) child.push_back({sub[v], v});
        sort(child.rbegin(), child.rend());
        if (child[0].first <= sz/2) {
            cent = u;
            P1 = child[0].second, P2 = child[1].second;
        }
    }
    dfs(cent);
    int ret = Query(add, P1, P2);
    if (ret == P1) ret = 1;
    else if (ret == P2) ret = 2;
    else ret = 0;
    vector<int> nxt;
    for (int i:vec) {
        if (mark[i] == ret) nxt.push_back(i);
        else exist[i] = false;
    }
    if (ret == 0) {
        nxt.push_back(P1); nxt.push_back(P2);
        exist[P1] = exist[P2] = true;
    }
    solve(add, nxt);
}

void Solve(int N) {
    n = N;
    adj[0].push_back(1), adj[1].push_back(0);
    added = {0, 1};
    for (int i=2;i<n;i++) {
        for (int j:added) exist[j] = true;
        solve(i, added);
    }

    set<pair<int,int>> ans;
    for (int i=0;i<n;i++) {
        for (int v:adj[i]) if (i < v) ans.insert({i, v});
    }
    for (auto [u, v]:ans) Bridge(u, v);
}

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