結果

問題 No.3024 全単射的
ユーザー tokitsukaze
提出日時 2025-02-14 22:10:38
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 486 ms / 5,000 ms
コード長 2,504 bytes
コンパイル時間 2,014 ms
コンパイル使用メモリ 180,212 KB
実行使用メモリ 50,460 KB
最終ジャッジ日時 2025-02-14 22:12:01
合計ジャッジ時間 5,548 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0