Submission #1012615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012615		pcc	Worst Reporter 2 (JOI16_worst_reporter2)	C++17	0 / 100	9 ms	19036 KiB

worst_reporter2

#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 (stderr)

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++){
      |                ~^~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40