///https://oj.uz/problem/view/JOI19_ho_t4
#include <bits/stdc++.h>
using namespace std;
#define int long long
#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],fx[M],fy[M];
int a[M][M];
int q[N];
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=INT_MAX;
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});
int 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};
}
reset(a,127);
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
joi2019_ho_t4.cpp: In function 'long long int calc(long long int)':
joi2019_ho_t4.cpp:45:13: warning: unused variable 's' [-Wunused-variable]
int u,v,s,t,mx=INT_MAX;
^
joi2019_ho_t4.cpp:45:15: warning: variable 't' set but not used [-Wunused-but-set-variable]
int u,v,s,t,mx=INT_MAX;
^
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(){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
31988 KB |
Output is correct |
| 2 |
Correct |
139 ms |
31992 KB |
Output is correct |
| 3 |
Correct |
73 ms |
31992 KB |
Output is correct |
| 4 |
Correct |
22 ms |
32120 KB |
Output is correct |
| 5 |
Execution timed out |
1093 ms |
31992 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
31988 KB |
Output is correct |
| 2 |
Correct |
139 ms |
31992 KB |
Output is correct |
| 3 |
Correct |
73 ms |
31992 KB |
Output is correct |
| 4 |
Correct |
22 ms |
32120 KB |
Output is correct |
| 5 |
Execution timed out |
1093 ms |
31992 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
31988 KB |
Output is correct |
| 2 |
Correct |
139 ms |
31992 KB |
Output is correct |
| 3 |
Correct |
73 ms |
31992 KB |
Output is correct |
| 4 |
Correct |
22 ms |
32120 KB |
Output is correct |
| 5 |
Execution timed out |
1093 ms |
31992 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
