Submission #1259612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259612		patgra	Love Polygon (BOI18_polygon)	C++20	100 / 100	180 ms	23896 KiB

polygon

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

constexpr int inf = 1e9 + 7;
int n;
vector<int> par, dp1, dp2, lft, comp, ansc; // 1 - points up, 2 - points down
vector<vector<int>> son;
vector<pair<int, int>> roots;
vector<bool> vis;
map<string, int> mp;

void dfsComp(int v, int c) {
    if(comp[v] == c) return;
    comp[v] = c;
    repIn(u, son[v]) if(u != v) dfsComp(u, c);
    dfsComp(par[v], c);
}

void dfsRoots(int v) {
    if(vis[v]) { roots[comp[v]] = {v, par[v]}; return; }
    vis[v] = true;
    dfsRoots(par[v]);
}

void calcdp(bool sec) {
    queue<int> q;
    rep(i, 1, n + 1) {
        if(son[i].empty() || (son[i].size() == 1 && par[i] == i)) dp1[i] = 0, dp2[i] = 1, lft[par[i]]--, lft[i] = 2;
        else lft[i] += (int)son[i].size() - (par[i] == i);
    }
    rep(i, 1, n + 1) if(lft[i] == 0) q.push(i);
    while(!q.empty()) {
        auto v = q.front();
        q.pop();
        dp1[v] = 0;
        repIn(u, son[v]) if(u != v) dp1[v] += dp2[u];
        dp2[v] = dp1[v] + 1;
        repIn(u, son[v]) if(u != v) dp2[v] = min(dp2[v], dp1[v] - dp2[u] + dp1[u] + 1);
        if(par[v] != v) lft[par[v]]--;
        if(par[v] != v && !lft[par[v]]) q.push(par[v]);
    }
    DEBUG {
        repIn2(k, v, mp) DC << k << ' ' << dp1[v] << ' ' << dp2[v] << eol;
    }
    rep(i, 1, (int)roots.size()) {
        if(par[roots[i].first] == roots[i].second && par[roots[i].second] == roots[i].first && roots[i].first != roots[i].second) {
            int sum = 0;
            repIn(j, son[roots[i].first]) if(j != roots[i].second && j != roots[i].first) sum += dp2[j];
            repIn(j, son[roots[i].second]) if(j != roots[i].first && j != roots[i].second) sum += dp2[j];
            ansc[i] = min(ansc[i], sum);
        }
        else ansc[i] = min(ansc[i], dp2[sec ? roots[i].second : roots[i].first]);
    }
    rep(i, 1, n + 1) lft[i] = 0;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int xd = 0;
    cin >> n;
    if(n % 2 == 1) { cout << -1; return 0; }
    par.resize(n + 1);
    son.resize(n + 1);
    dp1.resize(n + 1, inf);
    dp2.resize(n + 1, inf);
    lft.resize(n + 1);
    comp.resize(n + 1);
    vis.resize(n + 1);
    ansc.resize(n + 1, inf);
    roots.resize(1);
    string s1, s2;
    rep(i, 0, n) {
        cin >> s1 >> s2;
        if(!mp[s1]) { mp[s1] = ++xd; DC << s1 << ' ' << xd << eol; }
        if(!mp[s2]) { mp[s2] = ++xd; DC << s2 << ' ' << xd << eol; }
        par[mp[s1]] = mp[s2];
        son[mp[s2]].pb(mp[s1]);
    }

    rep(i, 1, n + 1) if(!comp[i]) {
        dfsComp(i, (int)roots.size());
        roots.pb({0, 0});
        dfsRoots(i);
    }

    DC << "Changes:\n";
    repIn2(a, b, roots) {
        if(a == 0 || a == b) continue;
        DC << ' ' << a << " -> " << a << eol;
        par[a] = a;
        vector<int> tmp;
        repIn(i, son[b]) if(i != a) tmp.pb(i);
        swap(tmp, son[b]);
        son[a].pb(a);
    }
    DC << eol;
    calcdp(0);

    DC << "Changes:\n";
    repIn2(a, b, roots) {
        if(a == 0 || a == b) continue;
        if(par[b] == a) {
            DC << ' ' << a << " -> " << b << eol;
            DC << ' ' << b << " -> " << a << eol;
            par[a] = b;
            repIn(i, son[a]) if(i != a && i != b) {
                DC << "  " << i << " -> " << i << eol;
                par[i] = i;
                son[i].pb(i);
            }
            repIn(i, son[b]) if(i != a && i != b) {
                DC << "  " << i << " -> " << i << eol;
                par[i] = i;
                son[i].pb(i);
            }
            continue;
        }
        DC << ' ' << a << " -> " << b << eol;
        DC << ' ' << b << " -> " << b << eol;
        son[a].pop_back();
        son[b].pb(a);
        son[b].pb(b);
        vector<int> tmp;
        repIn(i, son[par[b]]) if(i != b) tmp.pb(i);
        swap(tmp, son[par[b]]);
        par[a] = b;
        par[b] = b;
    }
    DC << eol;
    calcdp(1);


    int ans = 0;
    rep(i, 1, (int)roots.size()) ans += ansc[i];
    cout << ans << '\n';
}

• Subtask 1: 21 / 21
• Subtask 2: 25 / 25
• Subtask 3: 29 / 29
• Subtask 4: 25 / 25