Submission #941708

#	Time	Username	Problem	Language	Result	Execution time	Memory
941708		phoenix0423	Love Polygon (BOI18_polygon)	C++17	100 / 100	126 ms	12344 KiB

polygon

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int maxn = 2e5 + 5;
int to[maxn];
int indeg[maxn];
map<string, int> mp;
int cnt = 0;

signed main(void){
    fastio;
    int n;
    cin>>n;
    int ans = 0;
    for(int i = 0; i < n; i++){
        string a, b;
        cin>>a>>b;
        int id1 = (mp[a] ? mp[a] : mp[a] = ++cnt), id2 = (mp[b] ? mp[b] : mp[b] = ++cnt);
        to[id1] = id2;
        indeg[id2] ++;
    }
    if(n % 2){
        cout<<-1<<"\n";
        return 0;
    }
    vector<int> formed(n + 1);
    for(int i = 1; i <= n; i++){
        if(formed[i]) continue;
        if(to[i] != i && to[to[i]] == i){
            formed[i] = formed[to[i]] = 1;
        }
    }
    queue<int> q;
    for(int i = 1; i <= n; i++){
        if(!indeg[i]) q.push(i);
    }
    int left = 0;
    while(!q.empty()){
        int pos = q.front(); q.pop();
        if(formed[to[pos]]){
            left++;
            continue;
        }
        ans++;
        indeg[to[to[pos]]] --;
        if(!formed[to[to[pos]]] && !indeg[to[to[pos]]]) q.push(to[to[pos]]);
        formed[pos] = formed[to[pos]] = 1;
    }
    vector<int> vis(n + 1);
    for(int i = 1; i <= n; i++){
        if(!formed[i] && indeg[i] && !vis[i]){
            int tmp = to[i], len = 1;
            vis[i] = 1;
            while(tmp != i){
                vis[tmp] = 1, len++, tmp = to[tmp];
            }
            ans += len / 2, left += len % 2;
        }
    }
    cout<<ans + left<<"\n";
}

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