結果

問題 No.3024 全単射的
コンテスト
ユーザー vjudge1
提出日時 2025-02-15 01:30:13
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 544 ms / 5,000 ms
コード長 2,504 bytes
コンパイル時間 2,389 ms
コンパイル使用メモリ 212,300 KB
実行使用メモリ 47,420 KB
最終ジャッジ日時 2025-02-15 01:30:20
合計ジャッジ時間 6,317 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:123:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  123 |         scanf("%d%lld",&n,&m);
      |         ~~~~~^~~~~~~~~~~~~~~~
main.cpp:127:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  127 |                 scanf("%lld%lld",&x[i],&y[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAX=5e5+10;
const int mod=1e9;
struct Discretization
{
	#define type ll
	#define all(x) x.begin(),x.end()
	vector<type> a;
	void init(){a.clear();}
	void add(type x){a.push_back(x);}
	void work(){sort(all(a));a.resize(unique(all(a))-a.begin());}
	int get_pos(type x){return lower_bound(all(a),x)-a.begin()+1;}
	type get_val(int pos){return a[pos-1];}
	int size(){return a.size();}
	#undef type
	#undef all
}d;
struct Dinic
{
	#define type int
	const type inf=INF;
	static const int N=3e5+10;
	struct node
	{
		int from,to;
		type cap,flow;
		node(int u,int v,type c,type f):from(u),to(v),cap(c),flow(f){}
	};
	int n,s,t;
	vector<node> edge;
	vector<int> mp[N];
	int vis[N],dist[N],id[N];
	void init(int _n)
	{
		n=_n;
		edge.clear();
		for(int i=0;i<=n;i++)
		{
			mp[i].clear();
			id[i]=dist[i]=vis[i]=0;
		}
	}
	void add_edge(int from,int to,type cap)
	{
		edge.push_back(node(from,to,cap,0));
		edge.push_back(node(to,from,0,0));
		int m=edge.size();
		mp[from].push_back(m-2);
		mp[to].push_back(m-1);
	}
	bool bfs()
	{
		int i,x;
		memset(vis,0,sizeof vis);
		queue<int>q;
		q.push(s);
		dist[s]=0;
		vis[s]=1;
		while(!q.empty())
		{
			x=q.front();
			q.pop();
			for(i=0;i<mp[x].size();i++)
			{
				node &e=edge[mp[x][i]];
				if(!vis[e.to]&&e.cap>e.flow)
				{
					vis[e.to]=1;
					dist[e.to]=dist[x]+1;
					q.push(e.to);
				}
			}
		}
		return vis[t];
	}
	type dfs(int x,type a)
	{
		if(x==t||!a) return a;
		type flow=0,f;
		for(int &i=id[x];i<mp[x].size();i++)
		{
			node &e=edge[mp[x][i]];
			if(dist[x]+1==dist[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0)
			{
				e.flow+=f;
				edge[mp[x][i]^1].flow-=f;
				flow+=f;
				a-=f;
				if(!a) break;
			}
		}
		return flow;
	}
	type max_flow(int _s,int _t)
	{
		s=_s;
		t=_t;
		type res=0;
		while(bfs())
		{
			for(int i=0;i<=n;i++) id[i]=0;
			res+=dfs(s,inf);
		}
		return res;
	}
	#undef type
}dc; 
/*
O(n^2*m)
bipartite graph: O(m*sqrt(n))

dc.init(n);
dc.add_edge(a,b,cap); a,b: 1~n
*/
ll x[MAX],y[MAX];
int main()
{
	int n,i,s,t;
	ll m;
	scanf("%d%lld",&n,&m);
	d.init();
	for(i=1;i<=n;i++)
	{
		scanf("%lld%lld",&x[i],&y[i]);
		d.add(x[i]);
		d.add(y[i]);
	}
	d.work();
	s=n+d.size()+1;
	t=s+1;
	dc.init(t);
	for(i=1;i<=n;i++)
	{
		dc.add_edge(s,i,1);
		dc.add_edge(i,n+d.get_pos(x[i]),1);
		dc.add_edge(i,n+d.get_pos(y[i]),1);
	}
	for(i=1;i<=d.size();i++) dc.add_edge(n+i,t,1);
	printf("%d\n",dc.max_flow(s,t));
	return 0;
}
0