Submission #932926

#	Time	Username	Problem	Language	Result	Execution time	Memory
932926		asdasdqwer	Love Polygon (BOI18_polygon)	C++14	100 / 100	289 ms	27732 KiB

polygon

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

#define int int64_t

signed main() {
    int n;cin>>n;
    
    if (n % 2 != 0) {
        cout<<-1<<"\n";
        return 0;
    }

    map<string,int> mp;
    vector<vector<int>> in(n);
    vector<int> out(n);
    int cnt=0;
    for (int i=0;i<n;i++) {
        string s1, s2;cin>>s1>>s2;
        if (mp.find(s1) == mp.end()) {
            mp[s1] = cnt++;
        }

        if (mp.find(s2) == mp.end()) {
            mp[s2] = cnt++;
        }
        if (mp[s1] != mp[s2])
            in[mp[s2]].push_back(mp[s1]);
        out[mp[s1]] = mp[s2];
    }

    // remove all relationships (cycles of length 2)
    int swaps = n;
    vector<bool> vis1(n, false);

    for (int i=0;i<n;i++) {
        if (vis1[i])continue;
        if (out[out[i]] != i || out[i] == i) continue;
        vis1[i] = true;
        vis1[out[i]] = true;
        for (auto &x:in[i]) {
            out[x] = x;
        }

        for (auto &x:in[out[i]]) {
            out[x] = x;
        }

        swaps -= 2;
    }

    // get rid of all cycles of length 1 (people that love themselves), and the respective lines connected to them
    vector<int> dpWith(n, 0), dpWithout(n, 0);
    function<void(int)> dfs1=[&](int node) {
        vis1[node] = true;
        int sm = 0;
        for (auto &x:in[node]) {
            dfs1(x);
            dpWithout[node] += max(dpWith[x], dpWithout[x]);
            sm += max(dpWith[x], dpWithout[x]);
        }

        for (auto &x:in[node]) {
            dpWith[node] = max(dpWith[node], sm - max(dpWith[x], dpWithout[x]) + dpWithout[x] + 1);
        }
    };

    for (int i=0;i<n;i++) {
        if (out[i] == i && !vis1[i]) {
            dfs1(i);
            swaps -= max(dpWith[i], dpWithout[i]);
        }
    }

    // find all nodes that are part of a cycle
    vector<bool> incycle(n, false);
    vector<int> stat(n, 0);
    vector<bool> vis = vis1;

    function<int(int)> dfs2=[&](int node) -> int {
        vis[node] = true;
        // still being processed
        stat[node] = 1;
        if (stat[out[node]] == 0) {
            int d = dfs2(out[node]);
            if (d != -1) {
                incycle[node] = true;
            }

            if (d == node) {
                d = -1;
            }
            stat[node] = 2;
            return d;
        }

        else if (stat[out[node]] == 1) {
            stat[node] = 2;
            incycle[node] = true;
            return out[node];
        }

        // finished processing
        stat[node] = 2;
        return -1;
    };

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

    // calculate dp values for all nodes in a cycle
    function<void(int)> dfs3=[&](int node) {
        int sm = 0;
        for (auto &x:in[node]) {
            if (incycle[x])continue;
            dfs3(x);
            dpWithout[node] += max(dpWith[x], dpWithout[x]);
            sm += max(dpWith[x], dpWithout[x]);
        }

        for (auto &x:in[node]) {
            if (incycle[x])continue;
            dpWith[node] = max(dpWith[node], sm - max(dpWith[x], dpWithout[x]) + dpWithout[x] + 1);
        }
    };

    for (int i=0;i<n;i++) {
        if (incycle[i]) {
            dfs3(i);
            swaps -= dpWith[i];
        }
    }

    vis.clear();
    vis.assign(n, false);

    for (int i=0;i<n;i++) {
        if (incycle[i] && !vis[i]) {
            int pt = i;
            vector<bool> pos;
            do {
                pos.push_back(dpWith[pt] == dpWithout[pt]);
                vis[pt] = true;
                pt = out[pt];
            } while (pt != i);
            
            vector<bool> tmp;
            while (pos.size() && pos.back() == true) {
                tmp.push_back(true);
                pos.pop_back();
            }

            for (bool x:pos) {
                tmp.push_back(x);
            }
            tmp.push_back(false);

            stack<bool> st;
            for (bool x:tmp) {
                if (x) {
                    st.push(x);
                }

                else {
                    swaps -= ((int)st.size() / 2);
                    while (st.size()) st.pop();
                }
            }
        }
    }

    cout<<swaps<<"\n";
}

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