Submission #7641019


Source Code Expand

Copy
#include<bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 200005;

struct mf{
	struct edg{ int pos, cap, rev; };
	vector<edg> gph[MAXN];
	void clear(){ for(int i=0; i<MAXN; i++) gph[i].clear(); }
	void add_edge(int s, int e, int x){
		gph[s].push_back({e, x, (int)gph[e].size()});
		gph[e].push_back({s, 0, (int)gph[s].size()-1});
	}
	int dis[MAXN], pnt[MAXN];
	bool bfs(int src, int sink){
		memset(dis, 0, sizeof(dis));
		memset(pnt, 0, sizeof(pnt));
		queue<int> que;
		que.push(src);
		dis[src] = 1;
		while(!que.empty()){
			int x = que.front();
			que.pop();
			for(auto &e : gph[x]){
				if(e.cap > 0 && !dis[e.pos]){
					dis[e.pos] = dis[x] + 1;
					que.push(e.pos);
				}
			}
		}
		return dis[sink] > 0;
	}
	int dfs(int x, int sink, int f){
		if(x == sink) return f;
		for(; pnt[x] < gph[x].size(); pnt[x]++){
			edg e = gph[x][pnt[x]];
			if(e.cap > 0 && dis[e.pos] == dis[x] + 1){
				int w = dfs(e.pos, sink, min(f, e.cap));
				if(w){
					gph[x][pnt[x]].cap -= w;
					gph[e.pos][e.rev].cap += w;
					return w;
				}
			}
		}
		return 0;
	}
	lint match(int src, int sink){
		lint ret = 0;
		while(bfs(src, sink)){
			int r;
			while((r = dfs(src, sink, 2e9))) ret += r;
		}
		return ret;
	}
}mf;

struct disj{
	int pa[MAXN];
	void init(int n){
		iota(pa, pa + n + 1, 0);
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		pa[q] = p; return 1;
	}
}AD, BD;

int n, A[MAXN], B[MAXN];

int main(){
	scanf("%d",&n);
	AD.init(n);
	BD.init(n);
	for(int i=0; i<n; i++){
		scanf("%d",&A[i]);
		AD.uni(i, A[i]);
	}
	for(int i=0; i<n; i++){
		scanf("%d",&B[i]);
		BD.uni(i, B[i]);
	}
	for(int i=0; i<n; i++){
		if(A[i] == i){
			mf.add_edge(2 * n, i, 1e9);
		}
		if(B[i] == i){
			mf.add_edge(i + n, 2 * n + 1, 1e9);
		}
		if(A[i] == B[i]){
			int ca = AD.find(i);
			int cb = BD.find(i);
			mf.add_edge(cb + n, ca, 1);
		}
		int ca = AD.find(i);
		int cb = BD.find(i);
		mf.add_edge(ca, cb + n, 1);
	}
	cout << -mf.match(2 * n, 2 * n + 1) + n << endl;
}

Submission Info

Submission Time
Task F - Two Permutations
User koosaga
Language C++14 (GCC 5.4.1)
Score 1600
Code Size 2258 Byte
Status AC
Exec Time 1681 ms
Memory 16000 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:79:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:83:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&A[i]);
                    ^
./Main.cpp:87:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&B[i]);
                    ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1600 / 1600
Status
AC × 3
AC × 22
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt
All 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 3 ms 7552 KB
01-02.txt AC 4 ms 7936 KB
01-03.txt AC 96 ms 14584 KB
01-04.txt AC 94 ms 14584 KB
01-05.txt AC 72 ms 14584 KB
01-06.txt AC 76 ms 14584 KB
01-07.txt AC 52 ms 14712 KB
01-08.txt AC 64 ms 14712 KB
01-09.txt AC 49 ms 14584 KB
01-10.txt AC 56 ms 14968 KB
01-11.txt AC 43 ms 14696 KB
01-12.txt AC 57 ms 16000 KB
01-13.txt AC 791 ms 13952 KB
01-14.txt AC 168 ms 16000 KB
01-15.txt AC 123 ms 14208 KB
01-16.txt AC 170 ms 14080 KB
01-17.txt AC 615 ms 13312 KB
01-18.txt AC 725 ms 13184 KB
01-19.txt AC 1681 ms 13312 KB
sample-01.txt AC 3 ms 7552 KB
sample-02.txt AC 3 ms 7552 KB
sample-03.txt AC 3 ms 7552 KB