Submission #386231

#	Time	Username	Problem	Language	Result	Execution time	Memory
386231		maximath_1	Love Polygon (BOI18_polygon)	C++11	100 / 100	306 ms	12644 KiB

polygon

#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <numeric>
#include <iostream>
#include <queue>
#include <assert.h>
#include <map>
#include <set>
#include <limits.h>
#include <random>
#include <chrono>
using namespace std;
 
#define ll long long
#define ld long double
const int MX = 200005;
const int BLOCK = 105;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
const int dxh[] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dyh[] = {2, -2, 2, -2, 1, -1, 1, -1}; // horse
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1}; // adj
const int dxd[] = {1, 1, 1, 0, -1, -1, -1, 0};
const int dyd[] = {1, 0, -1, -1, -1, 0, 1, 1}; // diag

int n, to[MX], indeg[MX], vis[MX], ans = 0;
vector<pair<int, int> > edge;
map<string, int> mp;
int mpid = 0;

int main(){
	cin.tie(0) -> sync_with_stdio(0);

	cin >> n; 
	if(n % 2){
		cout << -1 << endl;
		return 0;
	}

	string a, b;
	for(int i = 0; i < n; i ++){
		cin >> a >> b;
		if(!mp.count(a)) mp[a] = mpid ++;
		if(!mp.count(b)) mp[b] = mpid ++;
		int u = mp[a], v = mp[b];
		edge.push_back({u, v});

		indeg[v] ++;
		to[u] = v;
	}

	queue<int> lonely;
	for(int i = 0; i < n; i ++){
		if(!indeg[i]) lonely.push(i);
		if(to[i] != i && to[to[i]] == i)
			vis[i] = vis[to[i]] = 1;
	}

	for(; lonely.size();){
		int nw = lonely.front();
		lonely.pop();
		vis[nw] = 1;

		if(!vis[to[nw]]){
			vis[to[nw]] = 1;
			indeg[to[to[nw]]] --;
			if(!indeg[to[to[nw]]])
				lonely.push(to[to[nw]]);
		}
		ans ++;
	}

	for(int i = 0; i < n; i ++) if(!vis[i]){
		vis[i] = 1;
		int nw = i, cnt = 1;

		for(; !vis[to[nw]]; nw = to[nw], cnt ++)
			vis[to[nw]] = 1;

		ans += (cnt + 1) / 2;
	}

	cout << ans << endl;
	return 0;
}

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