Submission #645404

#	Time	Username	Problem	Language	Result	Execution time	Memory
645404		mychecksedad	Love Polygon (BOI18_polygon)	C++17	21 / 100	602 ms	1048576 KiB

polygon

/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;

int n, to[N], res = 0, dp[N][2];
string x, y;
vector<int> in(N), g[N];
map<string, int> s;
vector<bool> vis(N), is(N);

void dfs(int v, int d){
    vis[v] = 1;
    int u = to[v];
    if(vis[u]){
        if(d > 2) res += (d+1)/2;
        else if(d == 1) res++;
    }else dfs(u, d + 1);
}
void dfs1(int v){
    dp[v][0] = dp[v][1] = MOD;
    if(g[v].size() == 0){
        dp[v][0] = dp[v][1] = 1;
    }
    dp[v][0] = 1;
    int sum = 0;
    for(int u: g[v]){   
        dfs1(u);
        dp[v][0] += min(dp[u][0], dp[u][1]);
        sum += dp[u][1];
    }
    for(int u: g[v]){
        dp[v][1] = min(dp[v][1], sum - dp[u][1] + dp[u][0] - 1);
    }
}

void solve(){
    cin >> n;
    int c = 1;
    for(int i = 0; i < n; ++i){
        cin >> x >> y;
        if(s[x] == 0) s[x] = c++;
        if(s[y] == 0) s[y] = c++;
        int a = s[x] - 1, b = s[y] - 1;
        to[a] = b;
        is[b] = 1; 
        g[b].pb(a);
    }
    if(n&1){
        cout << -1;
        return;
    }
    if(n <= 20){
        int ans = n;
        for(int mask = 0; mask < (1<<n); ++mask){

            bool ok = 1;
            vector<int> v;

            for(int j = 0; j < n; ++j){
                if(!((1<<j)&mask)){
                    v.pb(to[j]);
                    if(to[j] == j) ok = 0;
                    else if(!(to[to[j]] == j || ((1<<to[j])&mask))) ok = 0;
                }
            }
            sort(all(v));
            
            for(int j = 0; j < int(v.size()) - 1; ++j) if(v[j] == v[j + 1]) ok = 0;
            

            if(ok){
                if(ans > __builtin_popcount(mask)){
                    ans = __builtin_popcount(mask);
                }
            }
        }
        cout << ans;
        return;
    }
    bool ok = 1;
    for(int i = 0; i < n; ++i) ok &= is[i];
    if(ok)
        for(int i = 0; i < n; ++i) if(!vis[i]) dfs(i, 1);
    else
        for(int i = 0; i < n; ++i) if(to[i] == i) dfs1(i), res += min(dp[i][0], dp[i][1]);
    cout << res;
}





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        cout << '\n';
    }
    return 0;
 
}

Compilation message (stderr)

polygon.cpp: In function 'void solve()':
polygon.cpp:92:7: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   92 |     if(ok)
      |       ^
polygon.cpp: In function 'int main()':
polygon.cpp:105:16: warning: unused variable 'aa' [-Wunused-variable]
  105 |     int T = 1, aa;
      |                ^~

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