Submission #645213

#	Time	Username	Problem	Language	Result	Execution time	Memory
645213		mychecksedad	Love Polygon (BOI18_polygon)	C++17	21 / 100	281 ms	14716 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];
string x, y;
vector<int> in(N);
map<string, int> s;
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++;
        to[s[x] - 1] = s[y] - 1;
        in[s[y] - 1]++;
    }
    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;
    }
    queue<int> q;
    vector<bool> vis(n+1);
    for(int i = 1; i <= n; ++i) if(in[i] == 0) q.push(i), vis[i] = 1;

    int self = 0, cc = 0;


    while(!q.empty()){
        int v = q.front();
        q.pop();
        int u = to[v];
        if(vis[u]){
            self++;
            continue;
        }
        vis[u] = 1;
        cc++;
        if(to[u] != u) q.push(to[u]);
    }

    cout << self * 2 + cc;
}





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 'int main()':
polygon.cpp:90:16: warning: unused variable 'aa' [-Wunused-variable]
   90 |     int T = 1, aa;
      |                ^~

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