oj.uz

Submission #598540

# Submission time Handle Problem Language Result Execution time Memory
598540 2022-07-18T13:27:03 Z urosk Love Polygon (BOI18_polygon) C++14
29 / 100
 204 ms 16484 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2676 KB Output is correct
7 Incorrect 2 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2680 KB Output is correct
3 Correct 1 ms 2676 KB Output is correct
4 Incorrect 173 ms 15800 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 15988 KB Output is correct
2 Correct 204 ms 15980 KB Output is correct
3 Correct 142 ms 15712 KB Output is correct
4 Correct 179 ms 15772 KB Output is correct
5 Correct 192 ms 15764 KB Output is correct
6 Correct 165 ms 16204 KB Output is correct
7 Correct 169 ms 16184 KB Output is correct
8 Correct 162 ms 16176 KB Output is correct
9 Correct 179 ms 16484 KB Output is correct
10 Correct 133 ms 15816 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 1 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2676 KB Output is correct
7 Incorrect 2 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -