Submission #579856

#	Time	Username	Problem	Language	Result	Execution time	Memory
579856		Mr_Husanboy	Love Polygon (BOI18_polygon)	C++14	25 / 100	294 ms	19276 KiB

polygon

// Muallif: Mansuraliyev Husanboy Murotali o'g'li  >> NamPS
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(a) a.begin(), a.end()
#define F first
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define S second
#define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
#define fm(a,i,c) for(int (a) = (i); (a) >= (c); (a)--)
// 0-9 >> 48-57;    A-Z>>65-90   and   a-z>>97-122 respectively;

const int MX=1e5+5;

vector<int> g[MX];
int vis[MX];

int dfs(int i){
	vis[i]=1;
	int s=0;
	for(auto u:g[i]){
		if(vis[u]==1){
			continue;
		}
		s+=dfs(u)+1;
	}
	vis[i]=2;
	return s;
}


void solve(){
	int n; cin>>n;
	map<string,int> mp;
	int cur=1;
	for(int i=0;i<n;i++){
		string a,b; cin>>a>>b;
		if(mp[a]==0) mp[a]=cur,cur++;
		if(mp[b]==0) mp[b]=cur,cur++;
		g[mp[a]].push_back(mp[b]);
	}
	if(n%2){
		cout<<"-1\n";return;
	}
	int k=0;
	ll ans=0;
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
		int s=dfs(i)+1;
		k+=s%2;
		if(s!=2)
		ans+=s/2;
	}
	cout<<ans+k<<"\n";
}
	

int main(){
	ios;
	solve();
}

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