Submission #770484

#	Time	Username	Problem	Language	Result	Execution time	Memory
770484		raysh07	Love Polygon (BOI18_polygon)	C++17	0 / 100	118 ms	11148 KiB

polygon

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

int n;
const int N = 1e5 + 69;
map <string, int> mp;
int c[N];
bool used[N];
int cnt = 0;

int f(string x){
	if (mp.find(x) != mp.end()) return mp[x];
	else return mp[x] = ++cnt;
}

void Solve()
{
	cin >> n;

	for (int i = 1; i <= n; i++){
		string u, v; cin >> u >> v;

		int a = f(u), b = f(v);
		c[a] = b;
	}

	if (n & 1){
		cout << -1 << "\n";
		return;
	}

	int ans = 0;
	for (int i = 1; i <= n; i++){
		if (c[i] != i && i == c[c[i]]){
			used[i] = true;
			used[c[i]] = true;
		}
	}

	for (int i = 1; i <= n; i++){
		if (!used[i] && c[i] != i && !used[c[i]]){
			used[i] = true;
			used[c[i]] = true;
			ans++;
		}
	}
    
	for (int i = 1; i <= n; i++){
		if (!used[i]) ans++;
	}
	
	cout << ans << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

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