Submission #1149164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149164		weakweakweak	Meetings (JOI19_meetings)	C++20	100 / 100	742 ms	920 KiB

meetings

// 官解作法
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
#define fs first 
#define sc second


int n;
vector<int> e[2010];
int invt[2010] = {0}; // whether in virtual tree yet
bool block[2010] = {0};
int sz[2010];

void deledge (int i, int j) {
    e[i].erase(find(e[i].begin(), e[i].end(), j));
    e[j].erase(find(e[j].begin(), e[j].end(), i));
}
void addedge (int i, int j) {
    if (i == j) {
        cout << "wtf\n";
        exit(0);
    }
    e[i].push_back(j);
    e[j].push_back(i);
}


int tt = 0;
int dfs (int i, int par) {
    if (block[i]) return sz[i] = 0;
    sz[i] = 1;
    for (int j : e[i]) if (j != par) sz[i] += dfs(j, i);
    return sz[i];
}

int dfs2 (int i, int par, int tsz) {
    if (block[i]) return -1;
    bool y = 1;
    for (int j : e[i]) {
        if (j == par) continue;
        int q = dfs2(j, i, tsz);
        if (q != -1) return q;
        if (sz[j] > tsz/2) y = 0;
    }
    if (!y or tsz - sz[i] > tsz/2) return -1;
    return i;
}



void add (int rt, int ni) {
    int tsz = dfs(rt, rt);
    tt++;
    if (tsz == 1) {
        invt[ni] = 1;
        addedge(rt, ni);
        return;
    }
    else if (tsz == 2) {
        invt[ni] = 1;
        int j = -1;
        for (int cj : e[rt]) if (!block[cj]) j = cj;
        int q = Query(j, ni, rt);
        if (q == j or q == rt) {
            addedge(q, ni);
            return;
        }
        deledge(j, rt);
        addedge(j, q);
        addedge(rt, q);
        if (q != ni) {
            invt[q] = 1;
            addedge(q, ni);
        }
        return;       
    }

    int g = dfs2(rt, rt, tsz);
    dfs(g, -1);
    vector<pii> sons;
    for (int j : e[g]) if (!block[j]) sons.push_back({sz[j], j});
    sort(sons.begin(), sons.end()); reverse(sons.begin(), sons.end());

    for (int i = 0; i < sons.size(); i+=2) {
        if (i == sons.size()-1) {
            add(sons[i].sc, ni);
            return;
        }
        int s = sons[i].sc, t = sons[i+1].sc;
        int q = Query(s,t,ni);
        if (q == s or q == t) {
            invt[ni] = 1;
            block[g] = 1;
            add(q, ni);
            return;
        }
        if (q == g) {
            block[s] = block[t] = 1;
            continue; // 可能在別的子樹、也可能在還沒出現過的子樹
        }
        if (Query(s, q, g) == q) {
            deledge(s, g);
            addedge(s, q);
            addedge(g, q);
            invt[ni] = invt[q] = 1;
            if (q != ni) {
                addedge(ni, q);
            }
            return;
        }
        else {
            deledge(t, g);
            addedge(t, q);
            addedge(g, q);
            invt[ni] = invt[q] = 1;
            if (q != ni) {
                addedge(ni, q);
            }
            return;
        }
    }
    addedge(g, ni);
    invt[ni] = 1;
    return;
}


void Solve(int N) {
    n = N;
    for (int i = 0; i <= n; i++) {
        invt[i] = 0, block[i] = 0;
        e[i].clear();
    }
    invt[0] = invt[1] = 1;
    addedge(0,1);

    for (int i = 2; i < n; i++) {
        if (!invt[i]) {
            for (int j = 0; j < n; j++) block[j] = 0;
            add(0, i);
        }
    }

    for (int i = 0; i < n; i++) for (int j : e[i]) if (i < j) Bridge(i, j);
}

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