Submission #770642

#	Time	Username	Problem	Language	Result	Execution time	Memory
770642		dungz	Love Polygon (BOI18_polygon)	C++17	0 / 100	2 ms	2644 KiB

polygon

#pragma GCC optimize ("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define fi first
#define se second
#define endl '\n'
#define task "task"
#define task "task"
#define prll pair<ll,ll>
#define pb push_back
#define ld long double
const ll MIN=-1e18,MAX=1e18,MOD=1e9+7;
unordered_map<string,int> name;
int danh[100005];
unordered_map<int,bool> danh2;
vector<int> rev[100005];
int fuckup=0;
int adj[100005];
int ans=0;
vector<int> dfslist;
bool in[100005];
int dfs(int u)
{
	// cout<<u<<" ";
	in[u]=1;
	int remain=0;
	for(int i:rev[u])
	{
		if(!in[i]) remain+=dfs(i);
	}
	if(remain==0) 
	{
		fuckup+=1;
		return 1;
	}
	else if(remain==1)
	{
		fuckup-=1;
		ans+=1;
		return 0;
	}
	else
	{
		ans+=1;
		fuckup-=1;
		return 0;
	}
}
int main(){
	#ifndef ONLINE_JUDGE
   		freopen (task".inp", "r", stdin);
   		freopen (task".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	if(n%2==1)
	{
		cout<<-1;
		return 0;
	}
	int d=0;
	for(int i=1;i<=n;i++)
	{
		string s1,s2;
		cin>>s1>>s2;
		if(!name[s1]) 
		{
			name[s1]=++d;
			// cout<<s1<<" "<<d<<endl;
		}
		if(!name[s2])
		{
			name[s2]=++d;
			// cout<<s2<<" "<<d<<endl;
		}
		adj[name[s1]]=name[s2];
		rev[name[s2]].push_back(name[s1]);
	}
	for(int i=1;i<=n;i++)
	{
		if(!danh[i])
		{
			// cout<<i<<endl;
			vector<int> vec;
			vector<int> temp;
			danh2.clear();
			int u=i,d2=-1;
			while(!danh[u])
			{
				danh[u]=++d2;
				danh2[u]=1;
				vec.push_back(u);
				u=adj[u];
			}
			int d3=0;
			if(danh2[u])
			{
				for(int j=danh[u];j<=vec.size()-1;j++)
				{
					in[vec[j]]=1;
					if(rev[vec[j]].size()>1) temp.push_back(vec[j]);
					// cout<<"hahahahaha"<<" "<<vec[j]<<endl;
					++d3;
				}
				if(d3%2==1)
				{
					if(!temp.empty())
					{
						in[temp[0]]=0;
						dfslist.push_back(temp[0]);
						for(int k=1;k<temp.size();k++)
						{
							for(auto z:rev[temp[k]])
							{
								dfslist.push_back(z);
							}
						}
					}	
					else fuckup+=1;
				}
				else
				{
					for(auto k:temp)
					{
						for(auto z:rev[k])
						{
							if(!in[z]) dfslist.push_back(z);
						}
					}
				}
				if(d3!=2) ans+=d3/2;
			}
			// cout<<endl;
		}
	}
	// cout<<"hahahaha"<<endl;
	// for(auto i:dfslist)
	// {
	// 	cout<<i<<" ";
	// }
	// cout<<endl;
	for(auto i:dfslist)
	{
		dfs(i);
	}
	ans+=fuckup;
	// cout<<endl;
	cout<<ans;
}
/*

*/

Compilation message (stderr)

polygon.cpp: In function 'int main()':
polygon.cpp:100:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for(int j=danh[u];j<=vec.size()-1;j++)
      |                       ~^~~~~~~~~~~~~~
polygon.cpp:113:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |       for(int k=1;k<temp.size();k++)
      |                   ~^~~~~~~~~~~~
polygon.cpp:52:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |      freopen (task".inp", "r", stdin);
      |      ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
polygon.cpp:53:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |      freopen (task".out", "w", stdout);
      |      ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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