Submission #1259571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259571		Zbyszek99	Love Polygon (BOI18_polygon)	C++20	100 / 100	270 ms	31476 KiB

polygon

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

int nxt_[100001];
vi sons[100001];
int color[100001];
bool del[100001];

vi path;
vi cycle;

void dfs(int v)
{
    color[v] = 1;
    path.pb(v);
    if(color[nxt_[v]] == 0) dfs(nxt_[v]);
    else 
    {
        if(color[nxt_[v]] == 1)
        {
            while(path.back() != nxt_[v])
            {
                cycle.pb(path.back());
                path.pop_back();
            }
            cycle.pb(nxt_[v]);
            rep(i,siz(cycle)-1)
            {
                path.pb(1);
            }
        }
    }
    color[v] = 2;
    path.pop_back();
}

pii dfs_dp(int v)
{
    vector<pii> dp_sons;
    forall(it,sons[v])
    {
        if(!del[it])
        {
            dp_sons.pb(dfs_dp(it));
        }
    }
    int dp0 = 1;
    int dp1 = 0;
    int min_del = 0;
    forall(it,dp_sons)
    {
        dp1 += it.ff;
        dp0 += it.ff;
        min_del = min(min_del,-it.ff+it.ss);
    }
    dp0 += min_del;
    return {dp0,dp1};
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    int n;
    cin >> n;
    vector<pair<string,string>> pairs;
    map<string,int> m;
    rep(i,n)
    {
        string s1,s2;
        cin >> s1 >> s2;
        m[s1] = 1;
        m[s2] = 1;
        pairs.pb({s1,s2});
    }
    if(n % 2 == 1)
    {
        cout << "-1\n";
        return 0;
    }
    int cur = 0;
    forall(it,m)
    {
        m[it.ff] = cur++;
    }
    rep(i,n)
    {
        nxt_[m[pairs[i].ff]] = m[pairs[i].ss];
        sons[m[pairs[i].ss]].pb(m[pairs[i].ff]);
    }
    vector<pii> cycle_pairs;
    vi trees;
    int ans = 0;
    rep(i,n)
    {
        if(color[i] == 0)
        {
            cycle = {};
            dfs(i);
            if(siz(cycle) != 0)
            {
                if(siz(cycle) == 1) 
                {
                    cycle_pairs.pb({cycle[0],cycle[0]});
                }
                else if(siz(cycle) == 2)
                {
                    forall(it,sons[cycle[0]])
                    {
                        if(it != cycle[1])
                        {
                            trees.pb(it);
                        }
                    }
                    forall(it,sons[cycle[1]])
                    {
                        if(it != cycle[0])
                        {
                            trees.pb(it);
                        }
                    }
                }
                else
                {
                    cycle_pairs.pb({cycle[0],cycle[1]});
                }
            }
        }
    }
    forall(it,trees)
    {
        ans += dfs_dp(it).ff;   
    }
    forall(it,cycle_pairs)
    {
        del[it.ff] = 1;
        int ans1 = dfs_dp(it.ff).ff;
        del[it.ff] = 0;
        del[it.ss] = 1;
        int ans2 = dfs_dp(it.ss).ff;
        del[it.ss] = 0;
        ans += min({ans1,ans2});
    }
    cout << ans << "\n";
}

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