This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
map<string,int> mp;
string ss[100010],se[100010];
vector<int> g[100010],gb[100010];
queue<int> topo,bfs;
int in[100010],dp[100010][2],sum,ch[100010],dp2[100010];
void dfs(int i,int p){
for(auto x : gb[i]){
if(x==p||in[x]>0) continue;
dfs(x,i);
}
int mx=0;
for(auto x : gb[i]){
if(x==p||in[x]>0) continue;
dp[i][1]+=dp[x][0];
mx=max(mx,dp[x][1]-dp[x][0]);
}
dp[i][0]=mx+dp[i][1];
dp[i][1]++;
}
int findloop(vector<int> t){
int mx=0,temp,n=t.size(),i,j;
if(n==1) return 0;
if(n==2) {
return 2;
}
for(i=0;i<n;i++){
dp2[i]=t[i];
dp2[(i+1)%n]=max(dp2[i],t[(i+1)%n]);
for(j=i+2;j<n+i-1;j++){
dp2[j%n]=max(dp2[(j+n-1)%n],dp2[(j+n-2)%n]+t[j%n]);
}
mx=max(mx,dp2[(i+n-2)%n]);
}
for(auto x : t) printf("%d ",x);
printf("\n");
printf("%d\n",mx);
return mx;
}
int main(){
int n,i,j;
scanf("%d",&n);
for(i=1;i<=n;i++){
cin >> ss[i] >> se[i];
mp[ss[i]]=i;
}
if(n%2!=0){
printf("-1");
return 0;
}
for(i=1;i<=n;i++){
int sss=mp[ss[i]];
int sse=mp[se[i]];
g[sss].push_back(sse);
gb[sse].push_back(sss);
in[sse]++;
}
for(i=1;i<=n;i++){
if(in[i]==0) topo.push(i);
}
while(!topo.empty()){
i=topo.front();
topo.pop();
in[i]--;
for(auto x : g[i]){
in[x]--;
if(in[x]==0){
topo.push(x);
}
}
}
int cnt=0;
int ans=0;
for(i=1;i<=n;i++){
if(in[i]>0){
dfs(i,-1);
ans+=(dp[i][0]);
}
}
vector<int> t;
for(i=1;i<=n;i++){
if(in[i]>0){
if(ch[i]==0){
bfs.push(i);
ch[i]=1;
t.clear();
while(!bfs.empty()){
j=bfs.front();
bfs.pop();
int mx=0;
if(gb[j].size()>1) t.push_back(1);
else t.push_back(0);
for(auto x : g[j]){
if(ch[x]==0){
bfs.push(x);
ch[x]=1;
}
}
}
ans+=(findloop(t));
}
}
}
printf("%d\n",n-ans);
return 0;
}
/*
8
leonard emmy
ada emmy
isaac leonard
emmy pierre
pierre bernhard
bernhard emmy
sofia karl
karl sofia
20
1 12
2 18
3 17
4 5
5 12
6 11
7 11
8 9
9 13
10 8
11 3
12 9
13 2
14 16
15 19
16 5
17 13
18 7
19 15
20 15
*/
Compilation message (stderr)
polygon.cpp: In function 'int findloop(std::vector<int>)':
polygon.cpp:23:14: warning: unused variable 'temp' [-Wunused-variable]
23 | int mx=0,temp,n=t.size(),i,j;
| ^~~~
polygon.cpp: In function 'int main()':
polygon.cpp:91:25: warning: unused variable 'mx' [-Wunused-variable]
91 | int mx=0;
| ^~
polygon.cpp:73:9: warning: unused variable 'cnt' [-Wunused-variable]
73 | int cnt=0;
| ^~~
polygon.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
43 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
# | 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... |