Submission #204135

#	Time	Username	Problem	Language	Result	Execution time	Memory
204135		LittleFlowers__	Coin Collecting (JOI19_ho_t4)	C++14	8 / 100	756 ms	8920 KiB

joi2019_ho_t4

///https://oj.uz/problem/view/JOI19_ho_t4
#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
#define gg exit(0);

const int N=100010,
          M=2010;

int n;
int lf[N][2],rt[N][2];
int x[N],y[N];

int bx[M],by[M],X[M],Y[M];
int a[M][M];
int q[N];
long long fx[M],fy[M];

int L(int i,int j){
    return lf[i][j]==i ? i : L(lf[i][j],j);
}
int R(int i,int j){
    return rt[i][j]==i ? i : R(rt[i][j],j);
}

int xx,yy,nn;

int calc(int i){
    int u,v,s,t,mx=1<<15;
    if(x[i]<1){
        u=R(1,0), v=R(1,1);
        if(u<=n+n){
            if(mx>u-x[i] + abs(1-y[i])){
                mx=u-x[i] + abs(1-y[i]);
                xx=u, yy=1;
            }
        }
        if(v<=n+n){
            if(mx>v-x[i] + abs(2-y[i])){
                mx=v-x[i] + abs(2-y[i]);
                xx=v, yy=1;
            }
        }
    } else if(x[i]>n+n){
        u=L(n,0), v=L(n,1);
        if(u>0){
            if(mx>x[i]-u + abs(1-y[i])){
                mx=x[i]-u + abs(1-y[i]);
                xx=u, yy=2;
            }
        }
        if(v>0){
            if(mx>x[i]-v + abs(2-y[i])){
                mx=x[i]-v + abs(2-y[i]);
                xx=v, yy=1;
            }
        }
    } else{
        u=L(x[i],0), v=L(x[i],1);
        if(u>0){
            if(mx>x[i]-u + abs(1-y[i])){
                mx=x[i]-u + abs(1-y[i]);
                xx=u, yy=2;
            }
        }
        if(v>0){
            if(mx>x[i]-v + abs(2-y[i])){
                mx=x[i]-v + abs(2-y[i]);
                xx=v, yy=1;
            }
        }
        u=R(x[i],0), t=R(x[i],1);
        if(u<=n+n){
            if(mx>u-x[i] + abs(1-y[i])){
                mx=u-x[i] + abs(1-y[i]);
                xx=u, yy=1;
            }
        }
        if(v<=n+n){
            if(mx>v-x[i] + abs(2-y[i])){
                mx=v-x[i] + abs(2-y[i]);
                xx=v, yy=1;
            }
        }
    }
    return mx;
}

struct pt{
    int x,y;
}p[N];

void fix(){
    int dt=1<<15;
    for(int i=1;i<=nn;++i) if(bx[i]==1)
        for(int j=1;j<=nn;++j) if(by[j]==0)
            if(dt>fx[i]+a[i][j]-fy[j]) dt=fx[i]+a[i][j]-fy[j];
    for(int i=1;i<=nn;++i) if(bx[i]==0) fx[i]+=dt;
    for(int i=1;i<=nn;++i) if(by[i]==0) fy[i]+=dt;
}

void upd(int v) {
    int u,k;
    while(v>0) {
        u=by[v];
        k=X[u];
        X[u]=v;
        Y[v]=u;
        v=k;
    }
}

int bfs(int i){
    int L,R;
    q[L=R=1]=i;
    memset( by, 0, sizeof(by));
    memset( bx, 0, sizeof(bx));
    bx[i]=1;
    while(L<=R) {
        int u=q[L++];
        for(int v=1;v<=nn;++v) if(by[v]==0 && fx[u]+a[u][v]-fy[v]==0) {
            by[v]=u;
            if(Y[v]==0) {
                upd(v);
                return true;
            }
            q[++R]=Y[v];
            bx[Y[v]]=1;
        }
    }
    return false;
}


main(){
    #define task "coincollecting"
    //freopen(task".inp","r",stdin);
    //freopen(task".out","w",stdout);

    n=in;
    forinc(i,1,n+n){
        x[i]=in,y[i]=in;
    }

    forinc(j,0,1)
        forinc(i,1,n+n) lf[i][j]=rt[i][j]=i;

    priority_queue<ii,vector<ii>,greater<ii>> q;

    forinc(i,1,n+n)
        q.push({calc(i),i});

    long long tot=0;
    while(q.size()>1000){
        ii u=q.top(); q.pop();
        int tmp=calc(u.se);
        if(u.fi!=calc(u.se)){
            q.push({tmp,u.se});
            continue;
        }
        lf[xx][yy-1]=xx-1;
        rt[xx][yy-1]=xx+1;
        tot+=tmp;
    }
    while(q.size()){
        int i=q.top().se; q.pop();
        p[++nn]={x[i],y[i]};
    }
    forinc(i,1,n){
        if(rt[i][0]==i)
            p[++nn]={i,1};
        if(rt[i][1]==i)
            p[++nn]={i,2};
    }
    nn/=2;
    forinc(i,1,nn)
        forinc(j,1,nn) a[i][j]=1<<15;
    forinc(i,1,nn)
        forinc(j,1,nn){
            a[i][j]=abs(p[i].x-p[j+nn].x) + abs(p[i].y-p[j+nn].y);
        }
    forinc(i,1,nn)
        while(!bfs(i)) fix();
    for(int i=1;i<=nn;++i){
        tot+=a[i][X[i]];
    }
    cout<<tot;
}

Compilation message (stderr)

joi2019_ho_t4.cpp: In function 'int calc(int)':
joi2019_ho_t4.cpp:45:13: warning: unused variable 's' [-Wunused-variable]
     int u,v,s,t,mx=1<<15;
             ^
joi2019_ho_t4.cpp:45:15: warning: variable 't' set but not used [-Wunused-but-set-variable]
     int u,v,s,t,mx=1<<15;
               ^
joi2019_ho_t4.cpp: At global scope:
joi2019_ho_t4.cpp:151:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

• Subtask 1: 8 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63