Submission #716512

#	Time	Username	Problem	Language	Result	Execution time	Memory
716512		amir	Love Polygon (BOI18_polygon)	C++17	0 / 100	200 ms	18252 KiB

polygon

/*
<< in the name of ALLAH >>
*/

#include <bits/stdc++.h>

//#pragma strings(readonly)
//#pragma variable(var_name,NORENT)
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops,Ofast")
//#pragma GCC target("avx2,fma")
//#pragma GCC optimize("Ofast")

using namespace std;

typedef long long int ll ;
typedef pair<int , int> pii ;
typedef pair<ll , ll> pll ;
typedef double db ;

#define ps push_back
#define pb pop_back
#define mp make_pair
#define all(x) x.begin() , x.end() 
#define sz(x) (int)x.size() 
#define debug(a) cout<<"debug: "<<(#a)<<" = "<<a<<'\n'
#define debugAr(a) cout << "Array " << (#a) << " :\n" ;for (int TMP : a) cout << TMP << " " ; cout << '\n' 
#define noo(x) (int)__builtin_popcount(x)
#define lastone(x) (x)&(-x)
#define f first
#define s second


const int maxn = 1e5 + 5 ;
int n ;
int f[maxn] ;
string t[maxn] , tp[maxn] ;

int d[maxn] ;
bool vis[maxn] ;


bool eng(int v){
	return f[f[v]] == v ;
}


int main()
{
    ios::sync_with_stdio(false) ; cin.tie(NULL) ; cout.tie(NULL) ;
    //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 
    
    cin >> n ;
    
    
    vector<string > vec ;
    for (int i = 0 ; i < n ; i ++){
    	cin >> t[i] >> tp[i] ;
    	vec.ps(t[i]) ;
    	vec.ps(tp[i]) ;
	}
	if (n & 1){
    	cout << -1 << '\n' ;
    	return 0 ;
	}
	sort(all(vec)) ;
	
	vec.resize(unique(all(vec)) - vec.begin( ) ) ;
	
	for (int i = 0 ; i < n ; i ++){
		int v = lower_bound(all(vec) , t[i] ) - vec.begin() ;
		int u = lower_bound(all(vec) , tp[i] ) - vec.begin() ;
		f[v] = u ;
		d[u] ++ ;
	}
    
    multiset<pii > D ;
    
    int temp = 0 ;
	int ans = 0 ;
	
    for (int i = 0 ; i < n ; i ++){
    	D.insert(mp(d[i] , i )) ;
	}
	
	
	while (!D.empty() && D.rbegin()->f > 1 ){
		int v = D.begin()->s ;
		D.erase(D.begin()) ;
		
		int u = f[v] ;
		if (eng(u)){
			D.erase(mp(d[u] , u)) ;
			f[v] = -1 , d[u] -- ;
			D.insert(mp(d[u] , u)) ;
			
			if (temp) ans += 2 ;
			temp = 1-temp ;
		}
		else{
			int w = f[u] ;
			D.erase(mp(d[w] , w)) ;
			f[u] = v , d[w] -- , d[v] ++ ;
			D.insert(mp(d[w] , w)) ;
			D.insert(mp(d[v] , v)) ;
			ans ++ ;
		}
	}
	
	for (pii x : D){
		int v = x.s ;
		int u = v ;
		int c = 1 ;
		while (f[u] != v) u = f[u] , c ++ ;
		if (c == 2) continue ;
		int w = (int)(c / 2) ;
		ans += w ;
		if (c & 1){
			if (temp) ans += 2 ;
			temp = 1 - temp ;
		}
	}
	
	cout << ans << '\n' ;
    
}

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