Submission #598540

#	Time	Username	Problem	Language	Result	Execution time	Memory
598540		urosk	Love Polygon (BOI18_polygon)	C++14	29 / 100	204 ms	16484 KiB

polygon

#define here cerr<<"===========================================\n"
#include "bits/stdc++.h"
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;

#define maxn 100005
ll n;
vector<ll> g[maxn];
map<string,ll> mp;
ll it = 1;
ll f[maxn];
ll in[maxn];
bool vis[maxn];
vector<pll> edg;
int main(){
	daj_mi_malo_vremena
    cin >> n;
    for(ll i = 1;i<=n;i++){
        string x1,y1;
        cin >> x1 >> y1;
        if(mp[x1]==0) mp[x1] = it++;
        if(mp[y1]==0) mp[y1] = it++;
        ll x = mp[x1];
        ll y = mp[y1];
        in[y]++;
        f[x] = y;
        edg.pb({x,y});
    }
    if(n&1){
        cout<<-1<<endl;
        return 0;
    }
    queue<ll> q;
    ll ans = 0;
    for(ll i = 1;i<=n;i++){
        if(in[i]==0) q.push(i);
        if(i==f[f[i]]&&f[i]!=i) vis[i] = 1;
    }
    ll sami = 0;
    while(sz(q)){
        ll x = q.front();
        q.pop();
        ll y = f[x];
        if(!vis[y]&&!vis[x]&&x!=y){
            ans++;
            vis[x] = vis[y] = 1;
            in[f[y]]--;
            if(in[f[y]]==0) q.push(f[y]);
        }else{
            in[y]--;
            if(in[y]==0) q.push(y);
        }
    }
    for(ll i = 1;i<=n;i++){
        if(vis[i]) continue;
        ll x = i;
        while(vis[x]==0){
            ll y = f[x];
            if(vis[y]||(y==x)){
                sami++;
                break;
            }
            vis[x] = vis[y] = 1;
            ans++;
            x = f[y];
        }
    }
    ans+=sami;
    cout<<ans<<endl;
	return 0;
}
/*
8
leonard emmy
ada emmy
isaac leonard
emmy pierre
pierre bernhard
bernhard emmy
sofia karl
karl sofia

4
a c
b c
c d
d d

3
rocky scarlet
scarlet patrick
patrick rocky
*/

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