#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e5 + 100;
const ll mod = 1e9+7;
const ld PI = acos((ld)-1);
#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}
int n , cnt = 0;
map < string , int > mp;
vector < int > in[maxn];
int from[maxn] , to[maxn];
int out[maxn];
int selfloop = 0;
int din[maxn];
set < pii > burn;
void sub1(){
int ans = 21;
for(int i = 0 ; i < (1 << n) ; i ++){
bool ok = 1;
int mat[25];
ms(mat , -1);
for(int j = 0 ; j < n ; j ++){
if(i & (1 << j)){
if(from[j] == to[j])ok = 0;
if(mat[from[j]] ^ -1 and mat[from[j]] ^ to[j])ok = 0;
mat[from[j]] = to[j];
if(mat[to[j]] ^ -1 and mat[to[j]] ^ from[j])ok = 0;
mat[to[j]] = from[j];
}
}
if(ok)ans = min(ans ,n - __builtin_popcount(i));
}
dokme(ans);
}
int par[maxn];
int sz[maxn];
int getpar(int v){
return((par[v] == v) ? v : par[v] = getpar(par[v]));
}
void merge(int v , int u){
if((u = getpar(u)) == (v = getpar(v)))return;
par[v] = u;
sz[u] += sz[v];
}
void sub2(){
for(int i = 0 ; i < n ; i ++)
par[i] = i , sz[i] = 1;
for(int i = 0 ; i < n ; i ++)
merge(i , out[i]);
int ans = 0;
for(int i = 0 ; i < n ; i ++)
ans += sz[getpar(i)] / 2 , ans += sz[getpar(i)] == 2 , sz[getpar(i)] = 0;
dokme(n - ans);
}
int h[maxn];
bool dfs(int v){
bool ok = 1;
for(auto u : in[v]){
if(h[u] >= 0)return(0);
h[u] = h[v] + 1 , ok &= dfs(u);
}
return(ok);
}
bool val3(){
bool ok = 1;
ms(h , -1);
for(int i = 0 ; i < n ; i ++)
if(out[i] == i)
h[i] = 0 , ok &= dfs(i);
for(int i = 0 ; i < n ; i ++)
if(h[i] == -1)
ok = 0;
return(ok);
}
int dp[maxn][3]; // empty par child
bool done[maxn];
int solve(int v){
done[v] = 1;
for(auto u : in[v])if(burn.count({v, u}) == 0)
solve(u);
int sum = 0;
for(auto u : in[v])if(burn.count({v, u}) == 0){
dp[v][0] += max(dp[u][0] , dp[u][2]);
dp[v][1] += max(dp[u][0] , dp[u][2]);
sum += max(dp[u][0] , dp[u][2]);
}
for(auto u : in[v])if(burn.count({v, u}) == 0){
dp[v][2] = max(dp[v][2] , sum - max(dp[u][0] , dp[u][2]) + dp[u][1]);
}
dp[v][1]++;
return(max(dp[v][0] , dp[v][2]));
}
void sub3(){
int ans = 0;
for(int i = 0 ; i < n ; i ++)
if(out[i] == i)
ans += solve(i);
dokme(n - ans);
}
int Cycle = 0 , mark[maxn] , mark2[maxn];
vector < int > vis , cy;
void cyc(int v){
mark[v] = 2;
mark2[v] = 1;
vis.pb(v);
for(auto u : in[v]){
if(mark[u] == 1)cyc(u);
if(Cycle){
mark[v] = 3;
if(Cycle == -1)return;
cy.pb(v);
if(Cycle == v+1)Cycle = -1;
return;
}
if(mark[u] == 2){cy.pb(v);Cycle = u+1;return;}
if(mark[u] == 3)continue;
}
mark[v] = 3;
}
bool cycle[maxn];
vector < int > comp[maxn];
int32_t main(){
migmig;
cin >> n;
if(n%2)dokme(-1);
for(int i = 0 ; i < n ; i ++){
string a , b;
cin >> a >> b;
if(!mp.count(a))mp[a] = cnt++;
if(!mp.count(b))mp[b] = cnt++;
int u = mp[a] , v = mp[b];
from[i] = u , to[i] = v;
out[u] = v;
if(u == v)
selfloop++;
din[v] ++;
if(u^v)in[v].pb(u);
}
int ans = 0;
for(int i = 0 ; i < n ; i ++)if(out[i] == i)ans += solve(i);
for(int i = 0 ; i < n ; i ++)par[i] = i , sz[i] = i;
for(int i = 0 ; i < n ; i ++)merge(i , out[i]);
for(int i = 0 ; i < n ; i ++)cycle[i] = 1;
for(int i = 0 ; i < n ; i ++)if(din[i] != 1)cycle[getpar(i)] = 0;
for(int i = 0 ; i < n ; i ++){
if(cycle[getpar(i)])
ans += sz[getpar(i)] / 2 , ans += sz[getpar(i)] == 2 , sz[getpar(i)] = 0 , done[i] = 1;
}
for(int i = 0 ; i < n ; i ++)comp[getpar(i)].pb(i);
for(int i = 0 ; i < n ; i ++)if(comp[i].size() and !done[i]){
Cycle = 0;
cy.clear();
cyc(i);
int ki = cy.back();
for(auto u : cy){
if(din[u] == 1)ki = u;
}
burn.clear();
burn.insert({ki , out[ki]});
burn.insert({out[ki] , ki});
for(auto x: comp[i])done[x] = 1;
}
cout << n - ans;
return(0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 4 |
Runtime error |
10 ms |
10092 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
306 ms |
21784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 4 |
Runtime error |
10 ms |
10092 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
