이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
<< 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 ;
if (n & 1){
cout << -1 << '\n' ;
return 0 ;
}
vector<string > vec ;
for (int i = 0 ; i < n ; i ++){
cin >> t[i] >> tp[i] ;
vec.ps(t[i]) ;
vec.ps(tp[i]) ;
}
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' ;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |