Submission #716513

#	Time	Username	Problem	Language	Result	Execution time	Memory
716513		ajab_01	Love Polygon (BOI18_polygon)	C++17	0 / 100	2041 ms	18444 KiB

polygon

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
vector<int> g[N] , adj[N];
map<string , int> mp;
int ans , n , num , len;
bool deg[N] , vis[N] , ch = 1;

void dfs(int ver){
	vis[ver] = 1;
	len++;
	for(int i : g[ver]){
		if(vis[i]) continue;
		dfs(i);
	}
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 0 ; i < n ; i++){
		string a , b;
		cin >> a >> b;
		if(mp.find(a) == mp.end()) mp[a] = num++;
		if(mp.find(b) == mp.end()) mp[b] = num++;
		g[mp[a]].push_back(mp[b]);
		adj[mp[b]].push_back(mp[a]);
		deg[mp[b]] = 1;
	}
	if(n & 1){
		cout << -1 << '\n';
		return 0;
	}

	for(int i = 0 ; i < n ; i++)
		ch &= deg[i];

	if(ch){
		for(int i = 0 ; i < n ; i++){
			if(vis[i]) continue;
			len = 0;
			dfs(i);
			if(len == 2) continue;
			ans += len / 2;
			if(len & 1) ans++;
		}
		cout << ans << '\n';
	}

	vector<int> vec;
	for(int i = 0 ; i < n ; i++)
		if(g[i][0] == i)
			vec.push_back(i);

	vector<int> cy;
	for(int i : vec){
		if(adj[i].size() == 1)
			cy.push_back(1);
		int ver = (adj[i][0] == i ? adj[i][1] : adj[i][0]) , len = 1;
		while(adj[ver].size()){
			len++;
			ver = adj[ver][0];
		}
		cy.push_back(len);
	}

	int countt = 0;
	for(int i : cy){
		ans += i / 2;
		if(i & 1) countt++;
	}
	ans += countt;
	cout << ans << '\n';
	return 0;
}

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