Submission #1259570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259570		ewirlan	Love Polygon (BOI18_polygon)	C++20	100 / 100	133 ms	21156 KiB

polygon

//
#ifndef __SIZEOF_INT128__
  #define __SIZEOF_INT128__
#endif
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template <typename T> using oset =  tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define rep(i, p, k) for(int i(p); i < (k); ++i)
#define per(i, p, k) for(int i(p); i > (k); --i)
#define sz(x) (int)(x).size()
#define sc static_cast
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef __int128_t lll;
//#define int ll
template <typename T = int> using par = std::pair <T, T>;
#define fi first
#define se second
#define test int _number_of_tests(in()); while(_number_of_tests--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb emplace_back
struct Timer {
    string name{""};
    time_point<high_resolution_clock> end, start{high_resolution_clock::now()};
    duration<float, std::milli> dur;
    Timer() = default;
    Timer(string nm): name(nm) {}
    ~Timer() {
        end = high_resolution_clock::now(); dur= end - start;
        cout << "@" << name << "> " << dur.count() << " ms" << '\n';
    }
};
template <typename T = int> inline T in()
{
    static T x;
    std::cin >> x;
    return x;
}
std::string yn(bool b)
{
    if(b) return "YES\n";
    else return "NO\n";
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par);
template <typename T> std::ostream& operator<< (std::ostream& out, const std::vector <T>& wek)
{
    for(const auto& i : wek)out << i << ' ';
    return out;
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par)
{
    out << '{'<<par.first<<", "<<par.second<<"}";
    return out;
}
#define show(x) cerr << #x << " = " << x << '\n';
constexpr int maxn = 1e5 + 3;
int fo[maxn];
vector <int> ba[maxn];
bool byl[maxn], cyk[maxn];
bool pdp[maxn][2];
int dpb[maxn][2];
int dp(int w, bool b){
    if(pdp[w][b])return dpb[w][b];
    int s(0);
    int d(0);
    for(auto i: ba[w])if(!cyk[i]){
        int d0(dp(i, 0)), d1(dp(i, 1)+1);
        s += d1;
        d = min(d, d0-d1);
    }
    if(b == 1)s += d;
    pdp[w][b] = 1;
    return dpb[w][b] = s;
}
std::int32_t main()
{
    std::cout.tie(nullptr); //for luck
    std::cin.tie(nullptr); std::ios_base::sync_with_stdio(0);
    int n(in());
    map <string, int> mapa;
    auto imi = [&](){
        static int c(0);
        static string s; cin >> s;
        if(mapa.count(s))return mapa[s];
        return mapa[s] = c++;
    };
    rep(i, 0, n){
        int a(imi()), b(imi());
        fo[a] = b;
        ba[b].pb(a);
    }
    if(n % 2 == 1){
        cout << "-1\n";
        return 0;
    }
    vector <vector <int>> cy;
    rep(i, 0, n)if(!byl[i]){
        vector <int> v, w;
        int j(i);
        while(!byl[j]){
            byl[j] = 1;
            v.pb(j);
            j = fo[j];
            if(cyk[j])goto end;
        }
        w.pb(j);
        while(sz(v) && v.back() != j){
            w.pb(v.back());
            v.pop_back();
        }
        if(!sz(v))goto end;
        cy.pb(w);
        for(auto i: w)cyk[i] = 1;
        end:;
    }
    int o(0);
    for(auto v: cy){
        if(sz(v) == 1)o += 1 + dp(v[0], 1);
        if(sz(v) == 2)o += dp(v[0], 0) + dp(v[1], 0);
        if(sz(v) > 2){
            // cerr << v << ":\n";
            o += sz(v);
            vector <bool> m(sz(v));
            rep(i, 0, sz(v)){
                int d0(dp(v[i], 0)), d1(dp(v[i], 1));
                o += d1;
                m[i] = d0 == d1;    
                // cerr << v[i] << ": " << d1 << ' ' << d0 << '\n';
            }
            int p(0);
            rep(i, 0, sz(v))if(!m[i])p = i;
            rep(i, 0, sz(v))if(m[(p+i)%sz(v)] && m[(p+i+1)%sz(v)]){
                // cerr << v[i] << ' ' << v[(i+1)%sz(v)] << '\n';
                --o;
                m[(p+i)%sz(v)] = m[(p+i+1)%sz(v)] = 0;
            }
        }
    }
    cout << o << '\n';
    return 0;
}

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