oj.uz

Submission #959262

# Submission time Handle Problem Language Result Execution time Memory
959262 2024-04-07T18:39:01 Z Abdalaziz_Alshami Love Polygon (BOI18_polygon) C++17
25 / 100
 135 ms 12884 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 132 ms 12884 KB Output is correct
5 Correct 135 ms 12628 KB Output is correct
6 Correct 120 ms 12664 KB Output is correct
7 Correct 112 ms 12428 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 129 ms 12744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -