Submission #490603

#	Time	Username	Problem	Language	Result	Execution time	Memory
490603		radal	Love Polygon (BOI18_polygon)	C++14	100 / 100	481 ms	55004 KiB

polygon

#include <bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
typedef pair<long double,long double> pld;
const long long int N = 2e5+10,mod = 1e9+7,inf = 1e9,sq = 700,sig = 26;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
inline int poww(int n,int k){
    int c = 1;
    while (k){
        if (k&1) c = (1ll*c*n)%mod;
        n = (1ll*n*n)%mod;
        k >>= 1;
    }
    return c;
}
map<string,int> mp;
vector<int> in[N],out[N];
int o,ans;
bool vis[N];
int mark[N],comp[N],p[N];
bool b[N];
void sfd(int v){
    for (int u : in[v]){
        if (u == v || mark[u] == 2) continue;
        sfd(u);
        if (!vis[v] && !vis[u]){
            vis[v] = 1;
            p[v] = u;
            p[u] = v;
            vis[u] = 1;
            ans++;
            o--;
        }
    }
    if (!vis[v])
        o++;
    else if (mark[v] == 2)
        b[comp[v]] = 1;
}
void dfs(int v,int t){
    comp[v] = t;
    for (int u : out[v]) if (!comp[u]) dfs(u,t);
    for (int u : in[v]) if (!comp[u]) dfs(u,t);
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    if(n&1){
        cout << -1;
        return 0;
    }
    set<string> st;
    int sz = 0;
    rep(i,1,n+1){
        string s,t;
        cin >> s >> t;
        if (st.find(s) == st.end()){
            sz++;
            mp[s] = sz;
            st.insert(s);
        }
        if (st.find(t) == st.end()){
            sz++;
            mp[t] = sz;
            st.insert(t);
        }
        in[mp[t]].pb(mp[s]);
        out[mp[s]].pb(mp[t]);
    }
    int t = 0;
    rep(i,1,n+1){
        if(comp[i]) continue;
        int v = i;
        while (mark[v] == 0){
            mark[v] = 1;
            v = out[v][0];
        }
        int u = v;
        while (mark[u] != 2){
            mark[u] = 2;
            u = out[u][0];
        }
        t++;
        dfs(u,t);
    }

    rep(i,1,n+1)
        if (!vis[i] && mark[i] == 2)
            sfd(i);
    rep(i,1,n+1){
        if (mark[i] != 2) continue;
        if (out[out[i][0]][0] == i && i != out[i][0]){
            if (i > out[i][0]) continue;
            int v = out[i][0];
            if (!vis[i] && !vis[v])
                o -= 2;
            else if (vis[i] && vis[v])
                continue;
            else
                ans--;
            continue;
        }
        if (!b[comp[i]]){
            int s = 1;
            int v = out[i][0];
            while(v != i){
                s++;
                v = out[v][0];
                vis[v] = 1;
            }
            if (s == 2) o -= 2;
            else{
                if (s&1) o -= (s-1);
                else o -= s;
                ans += s/2;
            }
            b[comp[i]] = 1;
            continue;
        }
        if (!vis[i] || vis[out[i][0]]) continue;
        int v = out[i][0];
        while (vis[v] != 1){
            if (!vis[out[v][0]]){
                vis[v] = 1;
                vis[out[v][0]] = 1;
                p[v] = out[v][0];
                p[out[v][0]] = v;
                ans ++;
                o -= 2;
                v = out[out[v][0]][0];
            }
            else break;
        }
    }
    cout << o+ans;
    return 0;
}

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