#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
int DPd[MAXN][2];
int dokad[MAXN];
vector<int> graf[MAXN];
map<string, int> scal;
int T = 1;
int ans = 0;
int DP[MAXN];
int odw[MAXN];
vector<int> curr;
vector<int> cykl;
void znajdz(int a, int b){
bool c = false;
for(auto u : curr){
//cout << u << " curr\n";
if(u == a) c = true;
if(c) cykl.push_back(u);
if(u == b) c = false;
}
//cout << "end\n";
return;
}
void dfsrev(int v, int p){
if(odw[v] == 3) return;
//cout << v << " " << p << " rev\n";
odw[v] = 2;
for(auto u : graf[v]){
if(u == p) continue;
dfsrev(u, v);
}
return;
}
void dfscykl(int v, int p){
curr.push_back(v);
odw[v] = 1;
if(dokad[v] == v){
cykl = {v};
return;
}
if(odw[dokad[v]] == 1){
znajdz(dokad[v], v);
return;
}
else if(odw[dokad[v]] == 0){
dfscykl(dokad[v], v);
}
curr.pop_back();
odw[v] = 2;
return;
}
void dfsdp(int v, int p){
if(graf[v].size() == 1 and graf[v][0] == p){
DPd[v][0] = 0;
DPd[v][1] = 1;
return;
}
else if(graf[v].size() == 1 and p == -1){
DPd[v][0] = 0;
DPd[v][1] = 1e9;
return;
}
int S = 0;
int mi = 1e9;
for(auto u : graf[v]){
if(u == p or odw[u] == 3) continue;
dfsdp(u, v);
S += DPd[u][1];
mi = min(mi, DPd[u][0] - DPd[u][1]);
}
DPd[v][0] = S;
DPd[v][1] = min(S + 1, S + mi + 1);
return;
}
int obliczdp(){
DP[0] = 0;
DP[1] = DPd[cykl[0]][1];
for(int i = 2; i <= cykl.size(); ++i){
int x = cykl[i-1];
DP[i] = min(DPd[x][1] + DP[i-1], DPd[x][0] + (dokad[x] == cykl[i-2] ? 0 : 1) + DPd[cykl[i-2]][0] + DP[i-2]);
}
return DP[cykl.size()];
}
void solve(int start){
//cout << start << " st\n";
dfscykl(start, -1);
if(cykl.size() == 1){
for(auto g : graf[cykl[0]]){
dfsrev(g, cykl[0]);
}
dfsdp(cykl[0], cykl[0]);
ans += DPd[cykl[0]][1];
return;
}
if(dokad[cykl[0]] != cykl[1]){
reverse(cykl.begin(), cykl.end());
}
for(auto u : cykl){
odw[u] = 3;
}
for(auto u : cykl){
for(auto g : graf[u]){
dfsrev(g, u);
}
dfsdp(u, -1);
}
int tmp = obliczdp();
int st = cykl[0];
cykl.erase(cykl.begin());
cykl.push_back(st);
ans += min(tmp, obliczdp());
return;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
string s1, s2;
for(int i = 0; i < n; ++i){
cin >> s1 >> s2;
int i1, i2;
if(scal[s1] != 0) i1 = scal[s1];
else{
scal[s1] = T;
T++;
i1 = T-1;
}
if(scal[s2] != 0) i2 = scal[s2];
else{
scal[s2] = T;
i2 = T;
T++;
}
if(i1 != i2) graf[i2].push_back(i1);
dokad[i1] = i2;
}
if(n % 2 == 1){
cout << -1 << "\n";
return 0;
}
// for(auto u : scal){
// cout << u.first << " " << u.second << " scal\n";
// }
for(int i = 1; i <= n; ++i){
if(odw[i] != 0) continue;
cykl.clear();
curr.clear();
solve(i);
}
cout << ans << "\n";
return 0;
}
# | 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... |