#include <bits/stdc++.h>
using namespace std;
struct Dinic{
struct E{
int t,c,f;
E(int tt = 0,int cc = 0,int ff = 0):t(tt),c(cc),f(ff){}
};
vector<E> e;
vector<vector<int>> paths;
vector<int> lvl,ptr;
Dinic(int N){
paths.resize(N);
lvl = vector<int>(N,0);
ptr = vector<int>(N,0);
}
void add_edge(int a,int b,int f){
paths[a].push_back(e.size());
e.push_back(E(b,f,0));
paths[b].push_back(e.size());
e.push_back(E(a,0,0));
}
queue<int> q;
bool bfs(int s,int t){
fill(lvl.begin(),lvl.end(),-1);
lvl[s] = 0;
q.push(s);
while(!q.empty()){
auto now = q.front();
q.pop();
for(auto &eid:paths[now]){
if(e[eid].c-e[eid].f == 0)continue;
int nxt = e[eid].t;
if(lvl[nxt] == -1){
lvl[nxt] = lvl[now]+1;
q.push(nxt);
}
}
}
return lvl[t] != -1;
}
int dfs(int now,int t,int f){
if(now == t)return f;
for(int &i = ptr[now];i<paths[now].size();i++){
int eid = paths[now][i];
if(e[eid].c-e[eid].f == 0)continue;
int nxt = e[eid].t;
int re = dfs(nxt,t,min(f,e[eid].c-e[eid].f));
if(re){
e[eid].f += re;
e[eid^1].f -= re;
return re;
}
}
return 0;
}
int flow(int s,int t){
int ans = 0;
while(bfs(s,t)){
fill(ptr.begin(),ptr.end(),0);
int re;
while(re = dfs(s,t,INT_MAX)){
ans += re;
}
}
return ans;
}
};
#define pii pair<int,int>
#define fs first
#define sc second
#define _all(T) T.begin(),T.end()
const int mxn = 4e5+10;
vector<int> all;
pii arr[mxn],brr[mxn];
vector<int> vl[mxn],vr[mxn];
int N;
int solve(vector<int> &va,vector<int>&vb){
sort(_all(va));sort(_all(vb));
Dinic G(va.size()+vb.size()+2);
int s = 0,t = 1;
int sa = 2,sb = va.size()+2;
for(int i = 0;i<va.size();i++){
G.add_edge(s,i+sa,1);
}
for(int i = 0;i<vb.size();i++){
G.add_edge(i+sb,t,1);
if(i)G.add_edge(i+sb,i+sb-1,mxn);
}
for(int i = 0;i<va.size();i++){
int p = upper_bound(_all(vb),va[i])-vb.begin();
p--;
if(p>=0)G.add_edge(i+sa,p+sb,1);
}
return G.flow(s,t);
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>N;
for(int i = 0;i<N;i++)cin>>arr[i].fs>>arr[i].sc,all.push_back(arr[i].fs);
for(int i = 0;i<N;i++)cin>>brr[i].fs>>brr[i].sc,all.push_back(brr[i].fs);
sort(_all(all));all.resize(unique(_all(all))-all.begin());
for(int i = 0;i<N;i++){
arr[i].fs = lower_bound(_all(all),arr[i].fs)-all.begin();
brr[i].fs = lower_bound(_all(all),brr[i].fs)-all.begin();
vl[brr[i].fs].push_back(brr[i].sc);
vr[arr[i].fs].push_back(arr[i].sc);
}
int ans = N;
for(int i = 0;i<mxn;i++){
if(vl[i].empty()||vr[i].empty())continue;
ans -= solve(vl[i],vr[i]);
}
cout<<ans<<'\n';
}
Compilation message
worst_reporter2.cpp: In member function 'int Dinic::dfs(int, int, int)':
worst_reporter2.cpp:45:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int &i = ptr[now];i<paths[now].size();i++){
| ~^~~~~~~~~~~~~~~~~~
worst_reporter2.cpp: In member function 'int Dinic::flow(int, int)':
worst_reporter2.cpp:63:13: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
63 | while(re = dfs(s,t,INT_MAX)){
| ~~~^~~~~~~~~~~~~~~~~~
worst_reporter2.cpp: In function 'int solve(std::vector<int>&, std::vector<int>&)':
worst_reporter2.cpp:87:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int i = 0;i<va.size();i++){
| ~^~~~~~~~~~
worst_reporter2.cpp:90:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int i = 0;i<vb.size();i++){
| ~^~~~~~~~~~
worst_reporter2.cpp:94:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(int i = 0;i<va.size();i++){
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
