Submission #537257

#	Time	Username	Problem	Language	Result	Execution time	Memory
537257		surgutti	Love Polygon (BOI18_polygon)	C++14	100 / 100	273 ms	22732 KiB

polygon

#include <bits/stdc++.h>

using namespace std;

const int N = 100'007;

int n, p[N];
vector<int> adj[N];

map<string, int> id;
int get_id(const string &s) {
    return id.count(s) ? id[s] : id[s] = (int) id.size();
}

int vis[N];

pair<int, int> dfs(int u, int limit) {

    vis[u] = limit;

    int a = 0, b = 0;

    for (int v : adj[u]) if (vis[v] < limit) {
        auto [c, d] = dfs(v, limit);

        a += d;
        b = max(b, d - c);
    }

    // cerr << u << ": " << a << ' ' << a - b + 1 << '\n';
    return {a, a - b + 1};
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    cin >> n;

    if (n & 1) {
        cout << "-1\n";
        return 0;
    }

    for (int i = 0; i < n; i++) {
        string a, b; cin >> a >> b;
        int u = get_id(a), v = get_id(b);

        p[u] = v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int ans = 0;

    for (int i = 0; i < n; i++) if (!vis[i]) {
     
        int u = i;

        while (!vis[u]) {
            vis[u] = 1;
            u = p[u];
        }

        if (u == p[u]) {
            // cerr << "single meduse: " << u << '\n';
            ans += dfs(u, 3).second;
            continue;
        }
        
        int v = p[u];

        adj[u].erase(find(adj[u].begin(), adj[u].end(), v));
        adj[v].erase(find(adj[v].begin(), adj[v].end(), u));

        int res = 1;

        vis[u] = vis[v] = 2;

        for (int neigh : adj[u]) if (vis[neigh] != 2) {
            res += dfs(neigh, 2).second;
        }

        for (int neigh : adj[v]) if (vis[neigh] != 2) {
            res += dfs(neigh, 2).second;
        }

        // cerr << "cost in: " << u << ' ' << min(res - (u == p[p[u]]), dfs(u, 3).second) << '\n';
 
        ans += min(res - (u == p[p[u]]), dfs(u, 3).second);
    }

    cout << ans << '\n';
}

Compilation message (stderr)

polygon.cpp: In function 'std::pair<int, int> dfs(int, int)':
polygon.cpp:24:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |         auto [c, d] = dfs(v, limit);
      |              ^

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