#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
cerr<<vars<<" = ";
string delim="";
(...,(cerr<<delim<<values,delim=", "));
cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif
#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mxN=2e5+5; //make sure this is right
const int mod=1e9+7;
vector<string> all;
int get(string s){return lower_bound(all.begin(),all.end(),s)-all.begin()+1;}
int go[mxN],deg[mxN],p[mxN],colour[mxN],done[mxN],each[mxN][5],yes[mxN];
vector<int> component;
/*
red -> part of cycle
blue -> can be paired with non-red node
green -> points to red
yellow -> blue
pink -> part of 2 cycle
orange -> points to self
1 = red
2 = blue
3 = green
4 = yellow
5 = pink
6 = orange
*/
struct DSU{
int uf[mxN];
void init(){memset(uf,-1,sizeof(uf));}
int find(int x){return uf[x]<0?x:uf[x]=find(uf[x]);}
bool same(int x,int y){return find(x)==find(y);}
void unite(int x,int y){
x=find(x); y=find(y);
if(x==y)
return;
if(uf[x]>uf[y])
swap(x,y);
uf[x]+=uf[y]; uf[y]=x;
}
};
void dfs(int at){
component.pb(at);
int nxt=go[at];
done[at]=1;
if(nxt==at){
done[at]=2;
colour[at]=6;
return;
}
if(done[nxt]==1){
colour[at]=1;
colour[nxt]=7;
} else if(done[nxt]==2){
if(colour[nxt]==1)
colour[at]=3;
else
colour[at]=4;
} else{
dfs(nxt);
if(colour[nxt]==7){
colour[at]=3;
colour[nxt]=1;
} else if(colour[nxt]==1 && colour[at]!=7){
colour[at]=1;
} else if(colour[nxt]!=1){
colour[at]=4;
}
}
done[at]=2;
}
void change_yellow(int at){
if(colour[at]!=4)
return;
int nxt=go[at];
if(colour[nxt]==1 || colour[nxt]==2 || colour[nxt]==5)
return;
colour[at]=colour[nxt]=2;
change_yellow(go[nxt]);
}
DSU dsu;
int main(){
cin.sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n; cin>>n; dsu.init();
if(n&1){
cout<<-1<<"\n";
return 0;
}
vector<pair<string,string>> off;
for(int i=0;i<n;i++){
string s,t; cin>>s>>t;
all.pb(s); all.pb(t);
off.pb({s,t});
}
sort(all.begin(),all.end());
all.resize(unique(all.begin(),all.end())-all.begin());
for(auto &i:off){
int u=get(i.first);
int v=get(i.second);
go[u]=v;
deg[v]++;
deb(u,v);
if(go[v]==u && u!=v){
colour[v]=colour[u]=5;
done[u]=done[v]=2;
} else{
dsu.unite(u,v);
}
}
for(int i=1;i<=n;i++)
p[i]=i;
sort(p+1,p+1+n,[&](auto x,auto y){return deg[x]<deg[y];});
int ans=0;
for(int i=1;i<=n;i++){
if(!done[p[i]]){
component.clear();
deb(p[i]);
dfs(p[i]);
if(colour[p[i]]==4)
change_yellow(p[i]);
int rep=dsu.find(p[i]);
yes[rep]=1;
for(int &j:component){
deb(j,colour[j]);
each[rep][0]+=colour[j]==1;
each[rep][1]+=colour[j]==2;
each[rep][2]+=colour[j]==3;
each[rep][3]+=colour[j]==4;
each[rep][4]+=colour[j]==6;
}
}
}
for(int i=1;i<=n;i++){
if(!yes[i])
continue;
deb(each[i][0],each[i][1],each[i][2],each[i][3],each[i][4]);
ans+=each[i][0]/2+each[i][1]/2+each[i][2]+each[i][3]+each[i][4];
if(abs(dsu.uf[i])&1)
ans++;
}
cout<<ans<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
1100 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
176 ms |
20132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
1100 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
