Submission #55948786

---

Source Code Expand

// LUOGU_RID: 168483263
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#define int long long
using namespace std;
const int N=2e5+5,inf=0x3f3f3f3f3f3f3f3f;
int n,m,s,t,dep[N],p[N];
struct node{int x,v,id;};
vector<node> v[N];
void add(int x,int y,int val){
    int sti=v[x].size(),edi=v[y].size();
    v[x].push_back({y,val,edi});
    v[y].push_back({x,0,sti});
}
bool bfs(){
    queue<int> q;
    memset(dep,-1,sizeof(dep));
    memset(p,0,sizeof(p));
    q.push(s),dep[s]=0;
    while(!q.empty()){
        int top=q.front();q.pop();
        for(node i:v[top]){
            if(dep[i.x]==-1&&i.v){
                dep[i.x]=dep[top]+1;
                q.push(i.x);
            }
        }
    }
    return dep[t]!=-1;
}
int dfs(int x,int flow){
    int tmp=flow;
    if(x==t||!flow){
        return flow;
    }
    for(int id=p[x];id<v[x].size()&&tmp;id++){
        p[x]=id;
        node &i=v[x][id];
        if(dep[x]+1==dep[i.x]&&i.v>0){
            int t=dfs(i.x,min(i.v,tmp));
			if(!t){
                dep[i.x]=-1;
            }
			else{
                i.v-=t;
                v[i.x][i.id].v+=t;
                tmp-=t;
            }
        }

    }
    return flow-tmp;
}
int dinic(){
    int ans=0;
    while(bfs()){
        ans+=dfs(s,inf);
    }
    return ans;
}
int a[N],b[N],ans,f1[N],f2[N],tot;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n,ans=n,t=N-1;
    for(int i=1;i<=n;i++){
        cin>>a[i],a[i]++;
    }
    for(int i=1;i<=n;i++){
        cin>>b[i],b[i]++;
    }
    for(int i=1,x;i<=n;i++){
        if(!f1[i]){
            x=i,tot++;
            do{
                f1[x]=tot,x=a[x];
            }while(!f1[x]);
        }
        if(!f2[i]){
            x=i,tot++;
            do{
                f2[x]=tot,x=b[x];
            }while(!f2[x]);
        }
    }
    // for(int i=1;i<=n;i++) cout<<f1[i]<<' ';
    // cout<<'\n';
    for(int i=1;i<=n;i++){
        if(a[i]==i&&b[i]==i) ans--;
        else if(a[i]==i) add(f2[i],t,1);
        else if(b[i]==i) add(s,f1[i],1);
        else if(a[i]!=b[i]) add(f2[i],f1[i],1);
        else add(f2[i],f1[i],1),add(f1[i],f2[i],1);
    }
    cout<<ans-dinic()<<'\n';
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘long long int dfs(long long int, long long int)’:
Main.cpp:38:23: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<node>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   38 |     for(int id=p[x];id<v[x].size()&&tmp;id++){
      |                     ~~^~~~~~~~~~~~

Judge Result