제출 #1194361

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194361		Valters07	Love Polygon (BOI18_polygon)	C++20	100 / 100	178 ms	28544 KiB

polygon

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=native")
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define ld long double
#define en exit(0);
#define pb push_back
#define fi first
#define se second
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e5 + 5;
set<int> g[N];
int to[N], vis[N];
int dp[N][2];
pair<int,int> vert;
void dfs(int u)
{
    vis[u] = 1;
    int nxt = to[u];
    if(!vis[nxt])
        dfs(nxt);
    else if(vis[nxt] == 1)
        vert = {u, nxt};
    vis[u] = 2;
}
void dfs2(int u)
{
    dp[u][0] = dp[u][1] = 0;
    int dif = 0;
    for(auto v:g[u])
    {
        dfs2(v);
        dp[u][0] += dp[v][1];
        dp[u][1] += dp[v][1];
        dif = max(dif, dp[v][1] - dp[v][0]);
    }
    dp[u][1] += 1 - dif;
    dp[u][1] = min(dp[u][1], dp[u][0] + 1);
}
int try_from(int r)
{
    g[to[r]].erase(r);
    dfs2(r);
    g[to[r]].insert(r);
    return dp[r][1];
}
int main()
{
    fio
//    ifstream cin("in.in");
    int n;
    cin >> n;
    if(n&1)
        return cout << -1, 0;
    map<string, int> mp;
    int ind = 0;
    for(int i = 1;i <= n;i++)
    {
        string a, b;
        cin >> a >> b;
        if(!mp.count(a))
            mp[a] = ++ind;
        if(!mp.count(b))
            mp[b] = ++ind;
        int u = mp[a], v = mp[b];
        to[u] = v;
        g[v].insert(u);
    }
    int res = 0;
    for(int i = 1;i <= n;i++)
    {
        if(!vis[i])
        {
            vert = {-1, -1};
            dfs(i);
            if(vert.fi != -1)
            {
                if(to[vert.fi] == vert.se && to[vert.se] == vert.fi && vert.fi != vert.se)
                {
                    int cnt = 0;
                    for(auto v:g[vert.fi])
                        if(v != vert.se)
                            cnt += try_from(v);
                    for(auto v:g[vert.se])
                        if(v != vert.fi)
                            cnt += try_from(v);
                    res += cnt;
                }
                else
                {
                    int ans1 = try_from(vert.fi), ans2 = try_from(vert.se);
                    res += min(ans1, ans2);
                }
            }
        }
    }
    cout << res;
    return 0;
}

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