Submission #949685

#	Time	Username	Problem	Language	Result	Execution time	Memory
949685		lolismek	Love Polygon (BOI18_polygon)	C++14	0 / 100	241 ms	18124 KiB

polygon

#include <algorithm>
#include <iostream>
#include <climits>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>

#include <iomanip>
#include <cassert>

#include <random>
#include <chrono>

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using ull = unsigned long long;
using ll = long long;

//#define int __int128
//#define int ll
#define pii pair <int, int>
#define all(a) (a).begin(), (a).end()
#define fr first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound

#define vt vector
#define FOR(a, b) for(int i = (a); i <= (b); i++)
#define FORr(a, b) for(int i = (a); i >= (b); i--)
#define sz(x) (int)(x).size()

#define YES cout << "YES\n"
#define NO cout << "NO\n"

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rangerng(int l, int r){
    return uniform_int_distribution<>(l, r)(rng);
}

////////////////////////////////////////////////////////////////////////////////////

const int NMAX = 1e5;
const int INF = 1e9;

int to[NMAX + 1];
vt <int> in[NMAX + 1];

int viz[NMAX + 1];

int CYCID = 0;
int cycid[NMAX + 1];
vt <int> st;

void dfs(int node){
    viz[node] = 1;
    st.pb(node);

    if(viz[to[node]] == 0){
        dfs(to[node]);
    }else if(viz[to[node]] == 1){
        ++CYCID;
        while(st.back() != to[node]){
            cycid[st.back()] = CYCID;
            st.pop_back();
        }
        cycid[st.back()] = CYCID;
        st.pop_back();
    }

    viz[node] = 2;
}   

int dp[NMAX + 1][2];

void dfs2(int node, int par){
    int sum = 0;
    for(int vec : in[node]){
        if(vec != par && cycid[vec] == 0){
            dfs2(vec, node);
            sum += max(dp[vec][0], dp[vec][1]);
        }
    }
    dp[node][0] = dp[node][1] = sum;

    for(int vec : in[node]){
        if(vec != par && cycid[vec] == 0){
            dp[node][1] = max(dp[node][1], dp[node][1] + sum - max(dp[vec][0], dp[vec][1]) + dp[vec][1]);
        }
    }
}

int D[NMAX + 1][2];

void solve(){
    int n;
    cin >> n;

    int Id = 0;
    map <string, int> ids;
    for(int i = 1; i <= n; i++){
        string a, b;
        cin >> a >> b;
        if(ids[a] == 0){
            ids[a] = ++Id;
        }
        if(ids[b] == 0){
            ids[b] = ++Id;
        }
        to[ids[a]] = ids[b];
        in[ids[b]].pb(ids[a]);
    }

    for(int i = 1; i <= n; i++){
        if(!viz[i]){
            dfs(i);
        }
    }

    if(n & 1){
        cout << -1 << '\n';
        return;
    }

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

    for(int i = 1; i <= n; i++){
        viz[i] = 0;
    }

    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(cycid[i] != 0 && !viz[cycid[i]]){
            viz[cycid[i]] = 1;

            vt <int> aux;
            aux.pb(i);
            int node = to[i];
            while(node != i){
                aux.pb(node);
                node = to[node];
            }

            int tmp = 0;

            // cazul liber:

            D[aux[0]][0] = dp[aux[0]][0];
            D[aux[0]][1] = dp[aux[0]][1];
            for(int j = 1; j < sz(aux); j++){
                D[aux[j]][0] = max(D[aux[j - 1]][0], D[aux[j - 1]][1]) + dp[aux[j]][0];
                D[aux[j]][1] = max(D[aux[j - 1]][0], D[aux[j - 1]][1] + 1) + dp[aux[j]][1];
            }   
            tmp = max(D[aux.back()][0], D[aux.back()][1]);

            // cazul fortam muchie:

            D[aux[0]][0] = -INF;
            D[aux[0]][1] = dp[aux[0]][1];

            for(int j = 1; j < sz(aux); j++){
                D[aux[j]][0] = max(D[aux[j - 1]][0], D[aux[j - 1]][1]) + dp[aux[j]][0];
                D[aux[j]][1] = max(D[aux[j - 1]][0], D[aux[j - 1]][1] + 1) + dp[aux[j]][1];
            }

            tmp = max(tmp, D[aux.back()][1] + 1);

            ans += tmp;
        }
    }

    cout << n - ans << '\n';
}


signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int T;
    //cin >> T;

    T = 1;

    while(T--){
        solve();
    }

    return 0;
}

/*
8
1 2
3 2
4 1
2 5
5 6
6 2
7 8
8 7

4
1 3
2 3
3 4
4 4

3
1 2
2 3
3 1
*/

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