Submission #959262

#	Time	Username	Problem	Language	Result	Execution time	Memory
959262		Abdalaziz_Alshami	Love Polygon (BOI18_polygon)	C++17	25 / 100	135 ms	12884 KiB

polygon

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int vis[N],a[N],f[N];
int dfs(int x,int s)
{
	vis[x]=1;
	if(vis[a[x]]) return s/2+s%2;
	if(a[a[x]]==x) return s/2;
	return dfs(a[x],s+1);
}
signed main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin>>n;
	map<string,int>m;
	int d=1,ans=0;
	for(int i=0;i<n;i++)
	{
		string su,sv; cin>>su>>sv;
		int u,v;
		if(m[su]) u=m[su];
		else u=m[su]=d++;
		if(m[sv]) v=m[sv];
		else v=m[sv]=d++;
		a[u]=v; f[v]=1;
		if(a[v]==u){
			if(v==u) f[v]=1,f[u]=1;
			else vis[u]=vis[v]=f[u]=f[v]=1;
		}
	}
	if(n%2) { cout<<-1<<endl; return 0; }
	for(int i=1;i<=n;i++)
		if(!f[i]) ans+=dfs(i,1);
	for(int i=1;i<=n;i++)
		if(f[i]&&!vis[i]) ans+=dfs(i,1);
	cout<<ans<<endl;
}

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