Submission #1298153

#TimeUsernameProblemLanguageResultExecution timeMemory
1298153NotLinuxArcade (NOI20_arcade)C++20
51 / 100
1105 ms243932 KiB
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
bool dfs(int a, int L, vector<vector<int>>& g, vector<int>& btoa, vector<int>& A, vector<int>& B) {
	if (A[a] != L) return 0;
	A[a] = -1;
	for (int b : g[a]) if (B[b] == L + 1) {
		B[b] = 0;
		if (btoa[b] == -1 || dfs(btoa[b], L + 1, g, btoa, A, B))
			return btoa[b] = a, 1;
	}
	return 0;
}

int hopcroftKarp(vector<vector<int>>& g, vector<int>& btoa) {
	int res = 0;
	vector<int> A(g.size()), B(btoa.size()), cur, next;
	for (;;) {
		fill(all(A), 0);
		fill(all(B), 0);
		/// Find the starting nodes for BFS (i.e. layer 0).
		cur.clear();
		for (int a : btoa) if(a != -1) A[a] = -1;
		for(int a = 0;a<sz(g);a++) if(A[a] == 0) cur.push_back(a);

		/// Find all layers using bfs.
		for (int lay = 1;; lay++) {
			bool islast = 0;
			next.clear();
			for (int a : cur) for (int b : g[a]) {
				if (btoa[b] == -1) {
					B[b] = lay;
					islast = 1;
				}
				else if (btoa[b] != a && !B[b]) {
					B[b] = lay;
					next.push_back(btoa[b]);
				}
			}
			if (islast) break;
			if (next.empty()) return res;
			for (int a : next) A[a] = lay;
			cur.swap(next);
		}
		/// Use DFS to scan for augmenting paths.
		for(int a = 0;a<sz(g);a++)
			res += dfs(a, 0, g, btoa, A, B);
	}
}
void solve(){
    int n,m;
    cin >> n >> m;
    pair<int,int>arr[m];// time konum
    for(int i = 0;i<m;i++)cin >> arr[i].first;
    for(int i = 0;i<m;i++)cin >> arr[i].second;
    sort(arr , arr + m);
	vector<vector<int>>graph(m);
	for(int i = 0;i<m;i++){
		for(int j = i+1;j<m;j++){
			if(abs(arr[i].second - arr[j].second) <= abs(arr[i].first - arr[j].first)){
				graph[i].push_back(j);
			}
		}
	}
	vector<int>wtf(m,-1);
	cout << m - hopcroftKarp(graph , wtf) << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase=1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...