Submission #371528

#	Time	Username	Problem	Language	Result	Execution time	Memory
371528		mihai145	Love Polygon (BOI18_polygon)	C++14	100 / 100	261 ms	31760 KiB

polygon

//
// Created by mihai145 on 26.02.2021.
//

#include <iostream>
#include <vector>
#include <unordered_map>
#include <stack>
#include <algorithm>

using namespace std;

const int NMAX = 1e5;

int N, k;
unordered_map<string, int> names;

vector<int> g[NMAX + 5];
vector<int> bi[NMAX + 5];

bool solvedFor[NMAX + 5];

int Get(string s) {
    if (!names[s]) {
        names[s] = ++k;
    }

    return names[s];
}

void dfsConex(int node) {
    solvedFor[node] = true;
    for (int son : bi[node]) {
        if (!solvedFor[son]) {
            dfsConex(son);
        }
    }
}

vector<int> cycle;
bool inStack[NMAX + 5], cycleNode[NMAX + 5];
stack<int> st;

void dfsFindCycle(int node) {
    inStack[node] = true;
    st.push(node);

    for (int son : g[node]) {
        if (inStack[son] == true) {

            while (!st.empty() && st.top() != son) {
                cycle.push_back(st.top());
                cycleNode[st.top()] = true;
                st.pop();
            }

            cycle.push_back(st.top());
            cycleNode[st.top()] = true;

            return;

        } else {
            dfsFindCycle(son);
        }
    }
}

int dpTree[NMAX + 5][2], dpCycle[NMAX + 2][2];

void CalcDpTree(int node, int par = -1) {

    int nrSons = 0;

    for (int son : bi[node]) {
        if (son != par && !cycleNode[son]) {
            nrSons++;
            CalcDpTree(son, node);
        }
    }

    if (nrSons == 0) {
        dpTree[node][0] = dpTree[node][1] = 0;
    } else {

        int maxMatch = -N - 1;
        for (int son : bi[node]) {
            if (son != par && !cycleNode[son]) {
                dpTree[node][0] += max(dpTree[son][0], dpTree[son][1]);
                dpTree[node][1] += max(dpTree[son][0], dpTree[son][1]);
                maxMatch = max(maxMatch, -max(dpTree[son][0], dpTree[son][1]) + dpTree[son][0]);
            }
        }

        dpTree[node][1] += maxMatch;
        dpTree[node][1] += 1;
    }
}

int keeps;

void solve(int node) {
    dfsConex(node);

    while (!st.empty()) {
        st.pop();
    }
    cycle.clear();

    dfsFindCycle(node);

//    cout << "New cycle:\n";
//    for(auto it : cycle) {
//        cout << it << ' ';
//    }
//
//    cout << '\n' << '\n';

    for (int vert : cycle) {
        CalcDpTree(vert);
    }

    if ((int) cycle.size() == 1) {
        keeps += max(dpTree[cycle[0]][0], dpTree[cycle[0]][1]);
        return;
    }

    reverse(cycle.begin(), cycle.end());

    int maxKeeps = 0;

    ///we do not match the first node in the cycle with the last one
    dpCycle[cycle[0]][0] = dpTree[cycle[0]][0];
    dpCycle[cycle[0]][1] = dpTree[cycle[0]][1];
    for (int i = 1; i < (int) cycle.size(); i++) {
        int maxPrev = max(dpCycle[cycle[i - 1]][0], dpCycle[cycle[i - 1]][1]);
        dpCycle[cycle[i]][0] = maxPrev + dpTree[cycle[i]][0];
        dpCycle[cycle[i]][1] = max(maxPrev + dpTree[cycle[i]][1], dpCycle[cycle[i - 1]][0] + 1 + dpTree[cycle[i]][0]);
    }
    maxKeeps = max(dpCycle[cycle.back()][0], dpCycle[cycle.back()][1]);

    ///we match the first node in the cycle with the last one
    dpCycle[cycle[0]][0] = dpTree[cycle[0]][0];
    dpCycle[cycle[0]][1] = 0;
    for (int i = 1; i < (int) cycle.size(); i++) {
        int maxPrev = max(dpCycle[cycle[i - 1]][0], dpCycle[cycle[i - 1]][1]);
        dpCycle[cycle[i]][0] = maxPrev + dpTree[cycle[i]][0];

        if (i > 1) {
            dpCycle[cycle[i]][1] = max(maxPrev + dpTree[cycle[i]][1],
                                       dpCycle[cycle[i - 1]][0] + 1 + dpTree[cycle[i]][0]);
        } else {
            dpCycle[cycle[i]][1] = maxPrev + dpTree[cycle[i]][1];
        }
    }
    maxKeeps = max(maxKeeps, dpCycle[cycle.back()][1]);
    maxKeeps = max(maxKeeps, dpCycle[cycle.back()][0] + 1);


    if ((int) cycle.size() == 2) {
        maxKeeps = max(maxKeeps, 2 + dpTree[cycle[0]][0] + dpTree[cycle[1]][0]);
    }

    keeps += maxKeeps;
}

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

    cin >> N;

    if (N % 2 == 1) {
        cout << -1 << '\n';
        return 0;
    }

    for (int i = 1; i <= N; i++) {
        string s, t;
        cin >> s >> t;

        g[Get(s)].push_back(Get(t));

        bi[Get(s)].push_back(Get(t));
        bi[Get(t)].push_back(Get(s));
    }

    for (int i = 1; i <= N; i++) {
        if (!solvedFor[i]) {
            solve(i);
        }
    }

    cout << N - keeps << '\n';

    return 0;
}

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