#include <bits/stdc++.h>
using namespace std;
unordered_map <string, int> cod;
string s1, s2;
vector <int> fii[100001];
int urm[100001], next_cyc[100001];
bool viz[100001], verif[100001], done[100001];
int dp[100001][2], dp2[100001][2];
void dfs(int nod)
{
for(auto it:fii[nod])
dfs(it);
int max1 = -1e9;
for(auto it:fii[nod])
{
dp[nod][0] += max(dp[it][0], dp[it][1]);
dp[nod][1] += max(dp[it][0], dp[it][1]);
max1 = max(max1, dp[it][0] - max(dp[it][0], dp[it][1]));
}
if(fii[nod].size())
dp[nod][1] += 1 + max1;
}
int main()
{
#ifdef HOME
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif // HOME
int n, cnt = 0;
cin >> n;
if(n % 2)
{
cout << -1;
return 0;
}
for(int i = 1; i <= n; i++)
{
cin >> s1 >> s2;
if(!cod[s1])
cod[s1] = ++cnt;
if(!cod[s2])
cod[s2] = ++cnt;
urm[cod[s1]] = cod[s2];
}
/*for(int i = 1; i <= n; i++)
if(!viz[i])
{
int x = i;
do{
viz[x] = 1;
x = urm[x];
}while(!viz[x]);
int cx = x;
if(!verif[x])
{
do{
next_cyc[x] = urm[x];
x = urm[x];
}while(cx != x);
int x = i;
while(!next_cyc[x])
{
verif[x] = 1;
x = urm[x];
}
}
}
for(int i = 1; i <= n; i++)
if(!next_cyc[i])
fii[urm[i]].push_back(i);
for(int i = 1; i <= n; i++)
if(next_cyc[i])
dfs(i);
int rez = 0;
for(int i = 1; i <= n; i++)
if(next_cyc[i] && !done[i])
{
if(next_cyc[i] == i)
{
done[i] = 1;
rez += max(dp[i][0], dp[i][1]);
continue;
}
int max1;
///leg i si urm[i]
if(urm[urm[i]] == i)
max1 = dp[i][0] + dp[urm[i]][0] + 2;
else
{
dp2[urm[urm[i]]][0] = dp[urm[urm[i]]][0];
dp2[urm[urm[i]]][1] = max(dp[urm[urm[i]]][0], dp[urm[urm[i]]][0]);
for(int j = urm[urm[i]]; j != i; j = urm[j])
{
dp2[urm[j]][0] = dp[urm[j]][0] + max(dp2[j][0], dp2[j][1]);
dp2[urm[j]][1] = max(dp[urm[j]][1] + max(dp2[j][0], dp2[j][1]), dp[urm[j]][0] + dp2[j][0] + 1);
}
max1 = dp2[i][0] + dp[urm[i]][0] + 1;
}
///nu ii leg
dp2[urm[i]][0] = dp[urm[i]][0];
dp2[urm[i]][1] = dp[urm[i]][1];
for(int j = urm[i]; j != i; j = urm[j])
{
dp2[urm[j]][0] = dp[urm[j]][0] + max(dp2[j][0], dp2[j][1]);
dp2[urm[j]][1] = max(dp[urm[j]][1] + max(dp2[j][0], dp2[j][1]), dp[urm[j]][0] + dp2[j][0] + 1);
}
if(urm[urm[i]] != i)
rez += max(max1, max(dp2[i][0], dp2[i][1]));
else
rez += max(max1, max(dp[i][0], dp[i][1]) + max(dp[urm[i]][0], dp[urm[i]][1]));
int x = i;
while(!done[x])
{
done[x] = 1;
x = urm[x];
}
}
cout << n - rez;*/
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
118 ms |
10564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
