Submission #716542

#	Time	Username	Problem	Language	Result	Execution time	Memory
716542		amir	Love Polygon (BOI18_polygon)	C++17	29 / 100	316 ms	20068 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){
	if (v == f[v]) return 0 ;
	return (f[f[v]] == v) ;
}

map<string ,int > T ;

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] ;
    	T[t[i]] = 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[T[t[i]]] = T[tp[i]] ;
		d[T[tp[i]]] ++ ;
	}
	
	/*for (int v = 0 ; v < n ; v ++){
		cout << v << ">" << f[v] << '\n' ;
	}
	cout << '\n' ;*/
    
    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.begin()->f == 0){
		int v = D.begin()->s ;
		D.erase(D.begin()) ;
		
		int u = f[v] ;
		if (eng(u)){
			D.erase(D.find(mp(d[u] , u))) ;
			d[u] -- ;
			
			// f[v] = -1 ;
			D.insert(mp(d[u] , u)) ;
			
			temp ++ ;
		}
		else{
			int w = f[u] ;
			D.erase(D.find(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 ;
		if (f[v] == v){
			temp ++ ;
			continue ;
		}
		int u = v ;
		int c = 1 ;
		while (f[u] != v) u = f[u] , c ++ ;
		if (c == 2) continue ;
		int w = (int)(c >> 1) ;
		ans += w ;
		if (c & 1){
			temp ++ ;
		}
	}
	
	ans += temp ;
	cout << ans << '\n' ;
    
}

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