Submission #1259513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259513		inkvizytor	Love Polygon (BOI18_polygon)	C++20	100 / 100	215 ms	32076 KiB

polygon

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

#define ll long long

void licz(int v, vector<vector<int>> &r, vector<bool> &odw, vector<vector<int>> &dp) {
    odw[v] = 1;
    vector<vector<int>> p;
    for (int i : r[v]) {
        licz(i, r, odw, dp);
        p.push_back(dp[i]);
    }
    bool b = 1;
    int s = 0;
    for (auto x : p) {
        if (b && (x[0] == x[1])) {
            s += x[0]+1;
            b = 0;
        }
        else {
            s += x[1];
        }
    }
    dp[v][1] = s;
    dp[v][0] = s-(b^1);
}

void znajdz(int v, vector<int> &f, vector<vector<int>> &r, vector<bool> &odw, vector<vector<int>> &dp, int &w) {
    while (!odw[v]) {
        odw[v] = 1;
        v = f[v];
    }
    if (v == f[v]) {
        int b = 1;
        for (int u : r[v]) {
            if (u == v) {
                continue;
            }
            licz(u, r, odw, dp);
            if (b && (dp[u][0] == dp[u][1])) {
                w += dp[u][0]+1;
                b = 0;
            }
            else {
                w += dp[u][1];
            }
        }
        return;
    }
    if (f[f[v]] == v) {
        w += 2;
        for (int u : r[v]) {
            if (u == f[v]) {
                continue;
            }
            licz(u, r, odw, dp);
            w += dp[u][1];
        }
        for (int u : r[f[v]]) {
            if (u == v) {
                continue;
            }
            licz(u, r, odw, dp);
            w += dp[u][1];
        }
        return;
    }
    int x = 0;
    for (int i = 0; i < (int)r[f[v]].size(); i++) {
        if (r[f[v]][i] == v) {
            r[f[v]].erase(r[f[v]].begin()+i);
            break;
        }
    }
    licz(v, r, odw, dp);
    x = dp[v][1];
    int y = 1;
    for (int i = 0; i < (int)r[f[f[v]]].size(); i++) {
        if (r[f[f[v]]][i] == f[v]) {
            r[f[f[v]]].erase(r[f[f[v]]].begin()+i);
            break;
        }
    }
    for (int u : r[v]) {
        licz(u, r, odw, dp);
        y += dp[u][1];
    }
    for (int u : r[f[v]]) {
        licz(u, r, odw, dp);
        y += dp[u][1];
    }
    w += max(x, y);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    map<string, int> mp;
    int c = 0;
    vector<int> f (n);
    vector<vector<int>> r (n);
    for (int i = 0; i < n; i++) {
        string a, b;
        cin >> a >> b;
        int x, y;
        if (!mp.contains(a)) {
            mp[a] = c;
            c++;
        }
        if (!mp.contains(b)) {
            mp[b] = c;
            c++;
        }
        x = mp[a];
        y = mp[b];
        f[x] = y;
        r[y].push_back(x);
    }
    if (n%2) {
        cout << -1 << '\n';
        return 0;
    }
    vector<vector<int>> dp (n, vector<int> (2));
    int w = 0;
    vector<bool> odw (n, 0), odw2 (n, 0);
    for (int i = 0; i < n; i++) {
        if (!odw[i]) {
            znajdz(i, f, r, odw, dp, w);
        }
    }
    cout << n-w << '\n';
}

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