Submission #723949

#	Time	Username	Problem	Language	Result	Execution time	Memory
723949		_martynas	Love Polygon (BOI18_polygon)	C++11	100 / 100	137 ms	26740 KiB

polygon

#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()

using pii = pair<int, int>;
using vi = vector<int>;

const int MXN = 1e5+5;

int n;
string A[MXN], B[MXN];
vector<string> names;
int to[MXN];
vi from[MXN];
bool visited[MXN], in_stack[MXN];
int cycle[MXN], id = 1; // id == 0 => not in a cycle
int dp[2][MXN]; // dp[0] don't take, dp[1] take

void recur(int u) {
    if(from[u].empty()) {
        dp[0][u] = 0, dp[1][u] = 1;
        return;
    }
    int sum = 0;
    for(int v : from[u]) {
        if(cycle[v]) continue;
        recur(v);
        sum += dp[0][v];
    }
    dp[1][u] = sum+1;
    dp[0][u] = sum;
    for(int v : from[u]) {
        if(cycle[v]) continue;
        dp[0][u] = max(dp[0][u], sum-dp[0][v]+dp[1][v]);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> A[i] >> B[i];
        names.PB(A[i]);
    }
    sort(all(names));
    for(int i = 0; i < n; i++) {
        to[lower_bound(all(names), A[i]) - names.begin()] =
            lower_bound(all(names), B[i]) - names.begin();
    }
    if(n % 2) {
        cout << "-1\n";
        return 0;
    }
    for(int i = 0; i < n; i++) {
        from[to[i]].PB(i);
    }
    int ans = 0;
    for(int i = 0; i < n; i++) {
        if(visited[i]) continue;
        int u = i;
        vi st = {u};
        visited[u] = true;
        in_stack[u] = true;
        while(!visited[to[u]]) {
            st.PB(to[u]), u = to[u];
            visited[u] = true, in_stack[u] = true;
        }
        if(in_stack[to[u]]) {
            // new cycle
            vi nodes;
            int v = u;
            u = to[u];
            nodes.PB(v);
            cycle[v] = cycle[u] = id;
            while(u != v) nodes.PB(u), cycle[u] = id, u = to[u];
            id++;
            for(int a : nodes) recur(a);
            if(nodes.size() == 1) {
                ans += dp[0][nodes[0]];
            }
            else if(nodes.size() == 2) {
                ans += dp[1][nodes[0]]+dp[1][nodes[1]];
            }
            else {
                vector<vi> more_dp(2, vi(nodes.size(), -MXN));
                // more_dp[0][i] - i-th is changed
                // more_dp[1][i] - i-th is unchanged
                // 1st case:
                // first node is unchanged
                int mx = 0;
                more_dp[1][0] = dp[1][nodes[0]];
                for(int i = 1; i < nodes.size(); i++) {
                    more_dp[0][i] = max(more_dp[0][i], more_dp[1][i-1]+dp[1][nodes[i]]-1);
                    more_dp[0][i] = max(more_dp[0][i], more_dp[0][i-1]+dp[0][nodes[i]]);
                    more_dp[1][i] = max(more_dp[1][i], more_dp[0][i-1]+dp[1][nodes[i]]);
                }
                mx = more_dp[0][nodes.size()-1];
                more_dp = vector<vi>(2, vi(nodes.size(), -MXN));
                // 2nd case:
                // first node is changed
                more_dp[0][0] = dp[0][nodes[0]];
                for(int i = 1; i < nodes.size(); i++) {
                    more_dp[0][i] = max(more_dp[0][i], more_dp[1][i-1]+dp[1][nodes[i]]-1);
                    more_dp[0][i] = max(more_dp[0][i], more_dp[0][i-1]+dp[0][nodes[i]]);
                    more_dp[1][i] = max(more_dp[1][i], more_dp[0][i-1]+dp[1][nodes[i]]);
                }
                mx = max(mx, max(more_dp[0][nodes.size()-1],
                                 more_dp[1][nodes.size()-1]-dp[0][nodes[0]]+dp[1][nodes[0]]-1));
                ans += mx;
            }
        }
        else {
            // old part of tree
        }
        for(int v : st) in_stack[v] = false;
    }
    cout << n-ans << "\n";
    return 0;
}

Compilation message (stderr)

polygon.cpp: In function 'int main()':
polygon.cpp:98:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |                 for(int i = 1; i < nodes.size(); i++) {
      |                                ~~^~~~~~~~~~~~~~
polygon.cpp:108:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |                 for(int i = 1; i < nodes.size(); i++) {
      |                                ~~^~~~~~~~~~~~~~

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