Submission #643706

#	Time	Username	Problem	Language	Result	Execution time	Memory
643706		ParsaS	Love Polygon (BOI18_polygon)	C++14	100 / 100	471 ms	40204 KiB

polygon

// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
typedef long long ll;
const int N = 1e5 + 5, MOD = 1e9 + 7;
int n;
vector<int> adj[N];
map<string, int> M;
bool vis[N];
int cnt, par[N], h[N], C[3][N];
vector<int> V;

void dfs(int v) {
    vis[v] = true;
    cnt++;
    V.pb(v);
    for (auto u : adj[v]) {
        if (!vis[u]) {
            par[u] = v;
            h[u] = h[v] + 1;
            dfs(u);
        }
    }
}

void dfs2(int v) {
    vis[v] = true;
    C[2][v] = 1;
    int mx = 0;
    for (auto u : adj[v]) {
        if (vis[u])
            continue;
        dfs2(u);
        C[2][v] += C[1][u];
        C[0][v] += C[1][u];
        mx = max(mx, C[2][u] - C[1][u]);
    }
    C[1][v] = C[0][v] + mx;
    C[1][v] = max(C[1][v], C[0][v]);
}
int dp[N][3];
/*int DP(vector<int> vec) {
    assert(vec.empty());
    if (vec.empty()) {
        return 0;
    }
    for (int i = 0; i < vec.size(); i++) {
        int v = vec[i];
        dp[i] = (i ? dp[i - 1] : 0) + C[1][v];
        dp[i] = max(dp[i], (i - 1 ? dp[i - 2] : 0) + C[0][v] + (i ? C[1][vec[i - 1]] : 0));
    }
    return dp[(int)vec.size() - 1];
}*/

int SOLVE(int x) {
    V.clear();
    cnt = 0;
    dfs(x);
    int up = x, dn = x;
    bool ok = true;
    for (auto v : V) {
        int c = 0;
        for (auto u : adj[v]) {
            c += u == par[v];
            if (h[u] < h[v] - 1) {
                up = u;
                dn = v;
            }
            if (u == v) {
                ok = false;
                dn = up = v;
            }
        }
        if (c > 1) {
            dn = v;
            up = par[v];
        }
    }
    int xx = dn;
    vector<int> cle;
    while (dn != up) {
        cle.pb(dn);
        dn = par[dn];
    }
    cle.pb(up);
    for (auto v : V)
        vis[v] = false;
    for (auto v : cle)
        vis[v] = true;
    for (auto v : cle) {
        dfs2(v);
    }
    reverse(cle.begin(), cle.end());
    if (cle.size() == 1) {
        return max(C[0][up], C[1][up]);
    }
    if (cle.size() == 2) {
        return max(C[2][up] + C[2][xx], max(C[0][up], C[1][up]) + max(C[0][xx], C[1][xx]));
    }
    int v = cle.front();
    // 0:
    dp[0][0] = 0, dp[0][1] = 0; 

    for (int i = 1; i < cle.size(); i++) {
        int u = cle[i];
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + C[1][u];
        dp[i][1] = C[2][u] + (i > 1 ? C[0][cle[i - 1]] : 0) + (i > 2 ? max(dp[i - 2][1], dp[i - 2][0]) : 0);
    }
    int ans = max(dp[(int)cle.size() - 1][0], dp[(int)cle.size() - 1][1]) + C[0][v];
    // 1:
    dp[1][0] = max(C[0][cle[1]], C[1][cle[1]]);
    dp[1][1] = 0;
    for (int i = 2; i < cle.size(); i++) {
        int u = cle[i];
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + C[1][u];
        dp[i][1] = C[2][u] + (i > 1 ? C[0][cle[i - 1]] : 0) + (i > 2 ? max(dp[i - 2][1], dp[i - 2][0]) : 0);
    }
    ans = max(ans, max(dp[(int)cle.size() - 1][1], dp[(int)cle.size() - 1][0]) + C[1][v]);
    // 2:
    dp[1][0] = C[1][cle[1]];
    dp[1][1] = 0;
    for (int i = 2; i < cle.size(); i++) {
        int u = cle[i];
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + C[1][u];
        dp[i][1] = C[2][u] + (i > 1 ? C[0][cle[i - 1]] : 0) + (i > 2 ? max(dp[i - 2][1], dp[i - 2][0]) : 0);
    }
    ans = max(ans, C[0][cle.back()] + C[2][v] + max(dp[(int)cle.size() - 2][1], dp[(int)cle.size() - 2][0]));
    return ans;
}

void solve() {
    cin >> n;
    set<string> S;
    vector<pair<string, string> > tmp;
    for (int i = 0; i < n; i++) {
        string a, b; cin >> a >> b;
        tmp.pb(make_pair(a, b));
        S.insert(a), S.insert(b);
    }
    int inx = 0;
    for (auto s : S) {
        M[s] = ++inx;
    }
    for (auto [a, b] : tmp) {
        adj[M[a]].pb(M[b]);
        adj[M[b]].pb(M[a]);
    }

    if (n % 2) {
        cout << -1 << endl;
        return;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            ans += SOLVE(i);
        }
    }
    cout << n - ans << endl;
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();

    return 0;
}

Compilation message (stderr)

polygon.cpp: In function 'int SOLVE(int)':
polygon.cpp:107:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for (int i = 1; i < cle.size(); i++) {
      |                     ~~^~~~~~~~~~~~
polygon.cpp:116:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for (int i = 2; i < cle.size(); i++) {
      |                     ~~^~~~~~~~~~~~
polygon.cpp:125:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for (int i = 2; i < cle.size(); i++) {
      |                     ~~^~~~~~~~~~~~
polygon.cpp:63:10: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   63 |     bool ok = true;
      |          ^~
polygon.cpp: In function 'void solve()':
polygon.cpp:147:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  147 |     for (auto [a, b] : tmp) {
      |               ^

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