Submission #698220

#	Time	Username	Problem	Language	Result	Execution time	Memory
698220		mdbrnowski	Love Polygon (BOI18_polygon)	C++17	75 / 100	225 ms	28204 KiB

polygon

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

typedef vector<int> vi;

void change_edge(int a, int b, int c, vi& graph, vector<vi>& rgraph) {
    // a -> b    -->    a -> c
    graph[a] = c;
    rgraph[c].push_back(a);
    rgraph[b].erase(find(rgraph[b].begin(), rgraph[b].end(), a));
}

void dfs(int v, int prev, vector<vi>& rgraph, vi& dp_nope, vi& dp_yup) {
    dp_yup[v] = 0;
    int nope_minus_yup = 0;
    for (auto u : rgraph[v]) {
        if (u == prev) continue;  // important only for the first call
        dfs(u, v, rgraph, dp_nope, dp_yup);
        dp_yup[v] += dp_nope[u];
        nope_minus_yup = max(nope_minus_yup, dp_nope[u] - dp_yup[u]);
    }
    dp_nope[v] = 1 + dp_yup[v] - nope_minus_yup;
}

int calc(int start, vi& graph, vector<vi>& rgraph, vi& dp_nope, vi& dp_yup) {
    if (start == graph[start]) {
        dfs(start, graph[start], rgraph, dp_nope, dp_yup);
        return dp_nope[start];
    }
    dfs(graph[start], start, rgraph, dp_nope, dp_yup);
    dfs(start, graph[start], rgraph, dp_nope, dp_yup);
    return dp_yup[start] + dp_yup[graph[start]];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    map<string,int> names;
    int cur_name = 0;
    vi graph(n);
    vector<vi> rgraph(n);
    int res = 0;
    for (int i = 0; i < n; i++) {
        string a, b;
        cin >> a >> b;
        if (names.find(a) == names.end()) names[a] = cur_name++;
        if (names.find(b) == names.end()) names[b] = cur_name++;
        int A = names[a], B = names[b];
        graph[A] = B;
        rgraph[B].push_back(A);
    }
    if (n & 1) { cout << -1 << '\n'; return 0; }

    vi cycle_starters;
    int cc_number = 1;
    vi visited(n, 0);
    for (int i = 0; i < n; i++) {
        if (visited[i]) continue;
        visited[i] = cc_number;
        int j = graph[i];
        while (visited[j] == 0) {
            visited[j] = cc_number;
            j = graph[j];
        }
        if (visited[j] == cc_number)
            cycle_starters.push_back(j);
        cc_number++;
    }

    vi dp_nope(n),  // min number of arrows in subtree with root v if (v -> ) is changed
       dp_yup(n);   // min number of arrows in subtree with root v
    for (auto u : cycle_starters) {
        int cc_res = 1e9;
        int v = graph[u],
            w = graph[v],
            x = graph[w];
        if (u == v || u == w)
            cc_res = calc(v, graph, rgraph, dp_nope, dp_yup);
        else {
            change_edge(w, x, v, graph, rgraph);
            cc_res = min(cc_res, 1 + calc(v, graph, rgraph, dp_nope, dp_yup));
            change_edge(w, v, x, graph, rgraph);
            change_edge(v, w, u, graph, rgraph);
            cc_res = min(cc_res, 1 + calc(v, graph, rgraph, dp_nope, dp_yup));
            change_edge(v, u, w, graph, rgraph);
        }
        res += cc_res;
    }
    cout << res << '\n';
    return 0;
}

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