Submission #1127262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127262		Ludissey	Love Polygon (BOI18_polygon)	C++20	0 / 100	137 ms	8940 KiB

polygon

#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
using namespace std;
vector<int> a;
vector<int> req;
int n; 

vector<int> neigh;
vector<int> visited;
int rst=0;

void dfs(int x){
    if(neigh[x]==x||visited[neigh[x]]) {
        rst++;
        return;
    }
    visited[x]=true;
    visited[neigh[x]]=true;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    neigh.resize(n);
    visited.resize(n);
    map<string,int> mp;
    int t=0;
    for (int i = 0; i < n; i++)
    {
        string sa; string b; cin >> sa >> b;
        if(mp.find(sa)==mp.end()) mp[sa]=t++;
        if(mp.find(b)==mp.end()) mp[b]=t++;
        neigh[mp[sa]]=mp[b];
    }
    for (int i = 0; i < n; i++)
    {
        if(!visited[i]){
            dfs(i);
        }
    }
    if(n%2) cout << -1 << "\n";
    else cout << n/2+rst/2;

    return 0;
}

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