이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long
constexpr int maxN=1e5+5;
unordered_map<string,int> mp;
int n,cnt,adj[maxN],deg[maxN],subsz[maxN],odd[maxN],dp[2][maxN],cirdp[2][maxN],ans;
queue<int> q;
bitset<maxN> vis;
vector<int> jda[maxN];
void dfs(int now){
subsz[now]=1;
int sum=0;
for(int i:jda[now])if(!deg[i]){
dfs(i);
sum+=dp[0][i];
dp[1][now]+=max(dp[0][i],dp[1][i]);
}
for(int i:jda[now])if(!deg[i])dp[0][now]=max(dp[0][now],sum-dp[0][i]+dp[1][i]+1);
}
int main(){
cin>>n;
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++;
adj[mp[a]]=mp[b];
deg[mp[b]]++;
jda[mp[b]].emplace_back(mp[a]);
}
if(n&1)return cout<<-1,0;
ans=n;
fill(subsz,subsz+n,1);
for(int i = 0;i<n;i++)if(!deg[i])q.emplace(i);
for(int u;!q.empty();){
u=q.front(),q.pop();
if(!(--deg[adj[u]]))q.emplace(adj[u]);
}
for(int i = 0;i<n;i++)if(deg[i])dfs(i);
for(int i = 0;i<n;i++)if(deg[i]&&!vis[i]){
if(adj[i]==i)ans-=max(dp[0][i],dp[1][i]),vis[i]=1;
else if(adj[adj[i]]==i)ans-=dp[1][i]+dp[1][adj[i]]+2,vis[i]=1,vis[adj[i]]=1;
else {
int mxans=0;
{
int pos=adj[i],last=i;
cirdp[0][i]=max(dp[0][i],dp[1][i]);
cirdp[1][i]=dp[1][i];
vis[i]=1;
for(;pos!=i;last=pos,pos=adj[pos]){
vis[pos]=1;
cirdp[0][pos]=max(cirdp[1][last]+dp[1][pos]+1,cirdp[0][last]+max(dp[1][pos],dp[0][pos]));
cirdp[1][pos]=max(cirdp[0][last],cirdp[1][last])+dp[1][pos];
}
mxans=max(cirdp[0][last],cirdp[1][last]);
}
{
int pos=adj[i],last=i;
cirdp[0][i]=0;
cirdp[1][i]=-1e9;
for(;pos!=i;last=pos,pos=adj[pos]){
cirdp[0][pos]=max(cirdp[1][last]+dp[1][pos]+1,cirdp[0][last]+max(dp[1][pos],dp[0][pos]));
cirdp[1][pos]=max(cirdp[0][last],cirdp[1][last])+dp[1][pos];
}
cirdp[0][pos]=max(cirdp[1][last]+dp[1][pos]+1,cirdp[0][last]+max(dp[1][pos],dp[0][pos]));
cirdp[1][pos]=max(cirdp[0][last],cirdp[1][last])+dp[1][pos];
mxans=max({mxans,cirdp[0][pos],cirdp[1][pos]});
}
ans-=mxans;
}
}
cout<<ans;
}
# | 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... |