/*
<< 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]]] ++ ;
}
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 (vis[v]) continue ;
if (f[v] == v){
temp ++ ;
continue ;
}
int u = v ;
int c = 1 ;
while (f[u] != v) u = f[u] , c ++ , vis[u] = true ;
if (c == 2) continue ;
int w = (int)(c / 2) ;
ans += w ;
if (c & 1){
temp ++ ;
}
}
ans += temp ;
cout << ans << '\n' ;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
6484 KB |
Output is correct |
2 |
Correct |
3 ms |
6484 KB |
Output is correct |
3 |
Correct |
3 ms |
6484 KB |
Output is correct |
4 |
Correct |
4 ms |
6484 KB |
Output is correct |
5 |
Correct |
3 ms |
6484 KB |
Output is correct |
6 |
Correct |
4 ms |
6484 KB |
Output is correct |
7 |
Correct |
3 ms |
6484 KB |
Output is correct |
8 |
Correct |
5 ms |
6612 KB |
Output is correct |
9 |
Correct |
4 ms |
6484 KB |
Output is correct |
10 |
Correct |
4 ms |
6600 KB |
Output is correct |
11 |
Correct |
4 ms |
6484 KB |
Output is correct |
12 |
Correct |
4 ms |
6600 KB |
Output is correct |
13 |
Correct |
4 ms |
6484 KB |
Output is correct |
14 |
Correct |
5 ms |
6600 KB |
Output is correct |
15 |
Correct |
3 ms |
6484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
6484 KB |
Output is correct |
2 |
Correct |
4 ms |
6484 KB |
Output is correct |
3 |
Correct |
3 ms |
6484 KB |
Output is correct |
4 |
Correct |
202 ms |
19856 KB |
Output is correct |
5 |
Correct |
232 ms |
19968 KB |
Output is correct |
6 |
Correct |
240 ms |
19928 KB |
Output is correct |
7 |
Correct |
71 ms |
14308 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
250 ms |
19924 KB |
Output is correct |
2 |
Correct |
252 ms |
19932 KB |
Output is correct |
3 |
Correct |
171 ms |
19836 KB |
Output is correct |
4 |
Correct |
81 ms |
14284 KB |
Output is correct |
5 |
Correct |
262 ms |
19880 KB |
Output is correct |
6 |
Correct |
238 ms |
19936 KB |
Output is correct |
7 |
Correct |
259 ms |
19948 KB |
Output is correct |
8 |
Correct |
212 ms |
19976 KB |
Output is correct |
9 |
Correct |
237 ms |
19936 KB |
Output is correct |
10 |
Correct |
192 ms |
19488 KB |
Output is correct |
11 |
Correct |
4 ms |
6484 KB |
Output is correct |
12 |
Correct |
4 ms |
6484 KB |
Output is correct |
13 |
Correct |
4 ms |
6484 KB |
Output is correct |
14 |
Correct |
3 ms |
6484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
6484 KB |
Output is correct |
2 |
Correct |
3 ms |
6484 KB |
Output is correct |
3 |
Correct |
3 ms |
6484 KB |
Output is correct |
4 |
Correct |
4 ms |
6484 KB |
Output is correct |
5 |
Correct |
3 ms |
6484 KB |
Output is correct |
6 |
Correct |
4 ms |
6484 KB |
Output is correct |
7 |
Correct |
3 ms |
6484 KB |
Output is correct |
8 |
Correct |
5 ms |
6612 KB |
Output is correct |
9 |
Correct |
4 ms |
6484 KB |
Output is correct |
10 |
Correct |
4 ms |
6600 KB |
Output is correct |
11 |
Correct |
4 ms |
6484 KB |
Output is correct |
12 |
Correct |
4 ms |
6600 KB |
Output is correct |
13 |
Correct |
4 ms |
6484 KB |
Output is correct |
14 |
Correct |
5 ms |
6600 KB |
Output is correct |
15 |
Correct |
3 ms |
6484 KB |
Output is correct |
16 |
Correct |
3 ms |
6484 KB |
Output is correct |
17 |
Correct |
4 ms |
6484 KB |
Output is correct |
18 |
Correct |
3 ms |
6484 KB |
Output is correct |
19 |
Correct |
202 ms |
19856 KB |
Output is correct |
20 |
Correct |
232 ms |
19968 KB |
Output is correct |
21 |
Correct |
240 ms |
19928 KB |
Output is correct |
22 |
Correct |
71 ms |
14308 KB |
Output is correct |
23 |
Correct |
250 ms |
19924 KB |
Output is correct |
24 |
Correct |
252 ms |
19932 KB |
Output is correct |
25 |
Correct |
171 ms |
19836 KB |
Output is correct |
26 |
Correct |
81 ms |
14284 KB |
Output is correct |
27 |
Correct |
262 ms |
19880 KB |
Output is correct |
28 |
Correct |
238 ms |
19936 KB |
Output is correct |
29 |
Correct |
259 ms |
19948 KB |
Output is correct |
30 |
Correct |
212 ms |
19976 KB |
Output is correct |
31 |
Correct |
237 ms |
19936 KB |
Output is correct |
32 |
Correct |
192 ms |
19488 KB |
Output is correct |
33 |
Correct |
4 ms |
6484 KB |
Output is correct |
34 |
Correct |
4 ms |
6484 KB |
Output is correct |
35 |
Correct |
4 ms |
6484 KB |
Output is correct |
36 |
Correct |
3 ms |
6484 KB |
Output is correct |
37 |
Correct |
234 ms |
22124 KB |
Output is correct |
38 |
Correct |
268 ms |
22152 KB |
Output is correct |
39 |
Correct |
246 ms |
22032 KB |
Output is correct |
40 |
Correct |
281 ms |
22068 KB |
Output is correct |
41 |
Correct |
247 ms |
22124 KB |
Output is correct |
42 |
Correct |
264 ms |
22092 KB |
Output is correct |
43 |
Correct |
271 ms |
22088 KB |
Output is correct |
44 |
Correct |
243 ms |
22116 KB |
Output is correct |
45 |
Correct |
273 ms |
22028 KB |
Output is correct |
46 |
Correct |
230 ms |
22032 KB |
Output is correct |
47 |
Correct |
240 ms |
22256 KB |
Output is correct |
48 |
Correct |
241 ms |
22128 KB |
Output is correct |
49 |
Correct |
242 ms |
22120 KB |
Output is correct |
50 |
Correct |
199 ms |
22160 KB |
Output is correct |
51 |
Correct |
77 ms |
16560 KB |
Output is correct |
52 |
Correct |
209 ms |
22020 KB |
Output is correct |
53 |
Correct |
280 ms |
22032 KB |
Output is correct |
54 |
Correct |
250 ms |
22128 KB |
Output is correct |
55 |
Correct |
219 ms |
22032 KB |
Output is correct |
56 |
Correct |
246 ms |
22128 KB |
Output is correct |
57 |
Correct |
184 ms |
21576 KB |
Output is correct |
58 |
Correct |
4 ms |
6600 KB |
Output is correct |
59 |
Correct |
3 ms |
6600 KB |
Output is correct |
60 |
Correct |
4 ms |
6484 KB |
Output is correct |
61 |
Correct |
4 ms |
6484 KB |
Output is correct |
62 |
Correct |
5 ms |
6552 KB |
Output is correct |
63 |
Correct |
4 ms |
6484 KB |
Output is correct |
64 |
Correct |
4 ms |
6484 KB |
Output is correct |
65 |
Correct |
198 ms |
22136 KB |
Output is correct |
66 |
Correct |
213 ms |
22004 KB |
Output is correct |
67 |
Correct |
257 ms |
22068 KB |
Output is correct |
68 |
Correct |
76 ms |
16460 KB |
Output is correct |
69 |
Correct |
4 ms |
6612 KB |
Output is correct |
70 |
Correct |
3 ms |
6596 KB |
Output is correct |
71 |
Correct |
3 ms |
6484 KB |
Output is correct |
72 |
Correct |
4 ms |
6484 KB |
Output is correct |
73 |
Correct |
4 ms |
6484 KB |
Output is correct |
74 |
Correct |
4 ms |
6484 KB |
Output is correct |
75 |
Correct |
5 ms |
6604 KB |
Output is correct |
76 |
Correct |
3 ms |
6484 KB |
Output is correct |
77 |
Correct |
4 ms |
6580 KB |
Output is correct |
78 |
Correct |
4 ms |
6484 KB |
Output is correct |
79 |
Correct |
4 ms |
6484 KB |
Output is correct |
80 |
Correct |
3 ms |
6484 KB |
Output is correct |
81 |
Correct |
3 ms |
6572 KB |
Output is correct |
82 |
Correct |
3 ms |
6484 KB |
Output is correct |
83 |
Correct |
3 ms |
6596 KB |
Output is correct |