Submission #702251

#	Time	Username	Problem	Language	Result	Execution time	Memory
702251		Shreyan_Paliwal	Love Polygon (BOI18_polygon)	C++17	75 / 100	409 ms	25228 KiB

polygon

// #include <iostream>
// #include <vector>
// #include <map>
// using namespace std;

// const int maxn = 1e5 + 5;

// int n;
// int par[maxn];

// int vis[maxn];
// vector<int> cycle_starts;

// vector<int> adj[maxn];

// bool dfs_find_cycle(int nd) {
//     vis[nd] = 1; // current vertex visited

//     if (vis[par[nd]] == 0) { // if next vertex unvisited dfs_find_cycle into it
//         if (dfs_find_cycle(par[nd])) {
//             vis[nd] = 2;
//             return true;
//         }
//     } else if (vis[par[nd]] == 1) { // if visited next vertex in current iteration
//         cycle_starts.push_back(nd);
//         vis[nd] = 2;
//         return true; // back out
//     }

//     vis[nd] = 2; // mark current vertex visited
//     return false;
// }

// void find_components() {
//     for (int i = 0; i < n; i++) {
//         if (vis[i]) continue;
//         dfs_find_cycle(i);
//     }
// }

// void read_input() {
//     cin >> n;
    
//     map<string, int> m;
//     int cnt = 0;
//     for (int i = 0; i < n; i++) {
//         string a, b; cin >> a >> b;
//         // if (m.find(a) == m.end()) cout << a << ' ' << cnt << endl;
//         if (m.find(a) == m.end())
//             m[a] = cnt++;
//         // if (m.find(b) == m.end()) cout << b << ' ' << cnt << endl;
//         if (m.find(b) == m.end())
//             m[b] = cnt++;
//         par[m[a]] = m[b];

//         adj[m[a]].push_back(m[b]);
//         adj[m[b]].push_back(m[a]);
//     }
// }

// int cur_root = -1;

// int F[maxn], G[maxn];
// int f(int x, int par); int g(int x, int par);
// int f(int x, int par) {
//     F[x] = 1;
//     for (auto i : adj[x])
//         if (i != par && i != cur_root)
//             F[x] += g(i, x);
//     // cout << "f " << x << ' ' << F[x] << endl;
//     return F[x];
// }
// int g(int x, int par) {
//     G[x] = f(x, par) - 1;
//     int max_fg = 0;
//     for (auto i : adj[x])
//         if (i != par && i != cur_root)
//             max_fg = max(max_fg, f(i, x) - g(i, x));
//     G[x] += max_fg;
//     // cout << "g " << x << ' ' << G[x] << endl;
//     return G[x];
// }

// int main() {
//     // freopen("main.in", "r", stdin);

//     read_input();

//     if (n & 1) { cout << -1 << endl; return 0; }

//     find_components();

//     fill(F, F + maxn, -1);
//     fill(G, G + maxn, -1);
//     int sum_root_g = 0;
//     for (auto i : cycle_starts) {
//         // cycle starts @ i & size 1
//         if (i == par[i]) {
//             cur_root = i;
//             sum_root_g += g(i, i);
//         }

//         // size 2
//         else if (i == par[par[i]]) {
//             // cout << sum_root_g << ' ';
//             // optimal to take arc
//             // i, par[i]
//             for (auto j : adj[i])
//                 if (j != par[i])
//                     sum_root_g += g(j, i);
//             for (auto j : adj[par[i]])
//                 if (j != i)
//                     sum_root_g += g(j, par[j]);
//             sum_root_g += 2;
//             // cout << sum_root_g << endl;
//         }

//         else {
//             // cout << i << endl;
//             // par[i] --> ... --> i --> par[i]
//             cur_root = par[i];

//             // take arc
//             int with_arc = 1;
//             for (auto j : adj[i])
//                 if (j != par[i])
//                     with_arc += g(j, i);
//             for (auto j : adj[par[i]])
//                 if (j != i)
//                     with_arc += g(j, par[i]);
//             // cout << "with arc " << i << ' ' << par[i] << ' ' << with_arc << endl;

        
//             int without_arc = g(par[i], i);
//             // cout << "without arc " << i << ' ' << par[i] << ' ' << without_arc << endl;

//             sum_root_g += max(with_arc, without_arc);
//         }
//     }

//     cout << n - sum_root_g << endl;

//     return 0;
// }

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


const int maxn = 1e5 + 5;

int n;
int par[maxn];
vector<int> adj[maxn];

int vis[maxn];
vector<int> cyc_starts;

void read_input() {
    cin >> n; int cnt = 0;
    map<string, int> m;
    for (int i = 0; i < n; i++) {
        string a, b; cin >> a >> b;
        if (m.find(a) == m.end()) m[a] = cnt++;
        if (m.find(b) == m.end()) m[b] = cnt++;

        par[m[a]] = m[b];

        adj[m[a]].push_back(m[b]);
        adj[m[b]].push_back(m[a]);
    }
}

bool dfs(int nd) {
    vis[nd] = 1;

    if (vis[par[nd]] == 2) {vis[nd] = 2; return false;}
    if (vis[par[nd]] == 1) {
        cyc_starts.push_back(nd);
        vis[nd] = 2;
        return true;
    }

    bool ret = dfs(par[nd]);
    vis[nd] = 2;
    return ret;
}

void find_cycs() {
    for (int i = 0; i < n; i++) {
        if (vis[i]) continue;
        dfs(i);
    }
}

int cur_root = -1;

int F[maxn], G[maxn];
void rec_fg(int nd, int par) {
    F[nd] = 1, G[nd] = 0;
    for (auto i : adj[nd])
        if (i != par && i != cur_root) {
            // recurse 
            rec_fg(i, nd);
            F[nd] += G[i];
            G[nd] = max(G[nd], F[i] - G[i]);
        }
    G[nd] += F[nd] - 1;
    // cout << nd << ' ' << F[nd] << ' ' << G[nd] << endl;
}

int main() {
    // freopen("main.in", "r", stdin);

    read_input(); if (n & 1) { cout << -1 << endl; return 0; }
    find_cycs();

    int sum_s = 0;
    for (auto i : cyc_starts) {
        // cout << "---------------" << endl;
        // cout << i << endl;
        // if cycle size is 1
        if (i == par[i]) {
            cur_root = i;
            rec_fg(i, i);
            sum_s += G[i];
        } else if (i == par[par[i]]) {
            // children if i
            cur_root = -1;
            // cout << sum_s << endl;
            rec_fg(i, par[i]);
            for (auto j : adj[i])
                if (j != par[i])
                    sum_s += G[j];
            rec_fg(par[i], i);
            for (auto j : adj[par[i]])
                if (j != i)
                    sum_s += G[j];
            sum_s += 2;
            // cout << sum_s << endl;
        } else {
            // without arc i -- par[i]
            cur_root = par[i];
            rec_fg(par[i], i);
            int without_arc = G[par[i]];

            // with arc i -- par[i]
            int with_arc = 1;
            cur_root = i;
            rec_fg(par[i], i);
            for (auto j : adj[par[i]])
                if (j != i)
                    with_arc += G[j];
            // cout << "next" << endl;
            cur_root = par[i];
            rec_fg(i, par[i]);
            for (auto j : adj[i])
                if (j != par[i] && par[j] != i)
                    with_arc += G[j];
            // cout << without_arc << ' ' << with_arc << endl;
            sum_s += max(without_arc, with_arc);
        }
    }

    cout << n - sum_s << endl;
    return 0;
}

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