Submission #1189001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189001		onbert	Meetings (JOI19_meetings)	C++20	29 / 100	554 ms	864 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 (u == P1) cur += 1;
    else if (u == P2) cur += 2;
    mark[u] = cur;
    // cout << u << " " << cur << endl;
    for (int v:adj[u]) if (exist[v] && v != fa[u]) {
        fa[v] = u;
        dfs2(v);
    }
    if (u == P1) cur -= 1;
    else if (u == 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]) {
            bool done = false;
            for (int v:adj[ret]) {
                int val = Query(ret, v, add);
                if (val != ret) {
                    for (int &V:adj[ret]) if (V == v) V = val;
                    for (int &V:adj[v]) if (V == ret) V = val;
                    adj[val].push_back(ret); adj[val].push_back(v);
                    if (val != add) {
                        adj[val].push_back(add);
                        adj[add].push_back(val);
                        added.push_back(val);
                    }
                    done = true;
                    break;
                }
            }
            // cout << done << endl;
            // for (int i:adj[add]) cout << i << " "; cout << endl;
            if (!done) {adj[ret].push_back(add); adj[add].push_back(ret);}
            // cout << "ADD " << add << " " << done << endl;
            // cout << vec[0] << " " << vec[1] << endl;
            // cout << "test " << add << " " << ret << endl;
            // for (int i:adj[add]) cout << i << " "; cout << endl;
        } 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]);
            // cout << "add " << add << " " << vec[0] << " " << vec[1] << endl;
            // cout << ret << endl;
            if (ret != add) {
                adj[ret].push_back(add);
                adj[add].push_back(ret);
                added.push_back(ret);
            }
        }
        return;
    } else if (sz == 1) {
        int ret = vec[0];
        bool done = false;
        for (int v:adj[ret]) {
            int val = Query(ret, v, add);
            if (val != ret) {
                for (int &V:adj[ret]) if (V == v) V = val;
                for (int &V:adj[v]) if (V == ret) V = val;
                adj[val].push_back(ret); adj[val].push_back(v);
                if (val != add) {
                    adj[val].push_back(add);
                    adj[add].push_back(val);
                    added.push_back(val);
                }
                done = true;
                break;
            }
        }
        // cout << adj[add].size() << endl;
        if (!done) {adj[ret].push_back(add); adj[add].push_back(ret);}
        // cout << adj[add].size() << endl;
        // cout << "add. " << add << " " << vec[0] << " " << done << endl;
        // cout << adj[add].size() << endl;
        return;
    }

    int RT = vec[0];
    fa[RT] = -1;
    dfs(RT);
    for (int u:vec) {
        vector<pair<int,int>> child;
        for (int v:adj[u]) if (exist[v]) {
            if (v == fa[u]) child.push_back({sz - sub[u], v});
            else child.push_back({sub[v], v});
            // cout << u << " " << v << endl;
        }
        sort(child.rbegin(), child.rend());
        // if (u == 1) cout << "child " << child[0].first << " " << child[0].second << " " << child[1].first << endl;
        if (child[0].first <= sz/2) {
            cent = u;
            P1 = child[0].second, P2 = child[1].second;
        }
    }
    // cout << "TEST\n";
    // cout << add << endl;
    // for (int i:vec) cout << i << " "; cout << endl;
    // cout << cent << " " << P1 << " " << P2 << endl;
    fa[cent] = -1;
    dfs2(cent);
    int ret = Query(add, P1, P2);
    // cout << ret << endl;
    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;
    }
    solve(add, nxt);
}

void Solve(int N) {
    n = N;
    for (int i=0;i<n;i++) adj[i].clear();
    for (int i=0;i<n;i++) exist[i] = false;
    adj[0].push_back(1), adj[1].push_back(0);
    added = {0, 1};
    for (int i=2;i<n;i++) {
        // cout << "CHECK " << i << endl;
        // for (int u=0;u<n;u++) {for (int v:adj[u]) cout << v << " "; cout << endl;}
        // for (int j:added) cout << j << " "; cout << endl;
        for (int j:added) exist[j] = true;
        if (!exist[i]) {
            solve(i, added);
            added.push_back(i);
        }
        // cout << "test\n";
    }

    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) {
        // cout << u << " " << v << endl;
        Bridge(u, v);
    }
}

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