QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#431838#3179. Cordon BleujuancsAC ✓1259ms34788kbC++202.8kb2024-06-06 10:07:142024-06-06 10:07:14

Judging History

This is the latest submission verdict.

  • [2024-06-06 10:07:14]
  • Judged
  • Verdict: AC
  • Time: 1259ms
  • Memory: 34788kb
  • [2024-06-06 10:07:14]
  • Submitted

answer

#include <bits/stdc++.h>
#define el '\n'
#define forn(i, n) for(int i = 0; i < (int)n; ++i)
#define for1(i, n) for(int i = 1; i <= (int)n; ++i)
#define fore(i, l, r)for(int i = l; i <= (int)r; ++i)
#define fored(i, l, r)for(int i = r; i >= (int)l; --i)
#define all(a) a.begin(), a.end()
#define d(x) cerr<<#x<<" "<<x<<el
#define sz(x) x.size()
#define pb push_back
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef double ld;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef array<int, 4> a4;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
const ll INF=1e18;//for maximum set INF to 0, and negate costs
bool zero(ll x){return x == 0;}//change to x==0, for ints/ll
struct Hungarian{
    int n; vector<vll> cs; vi L, R;
    Hungarian(int N, int M):n(max(N,M)),cs(n,vll(n)),L(n),R(n){
        forn(x,N)forn(y,M)cs[x][y]=INF;
    }
    void set(int x,int y,ll c){cs[x][y]=c;}
	ll assign() {
		int mat = 0; vll ds(n), u(n), v(n); vi dad(n), sn(n);
		forn(i,n)u[i]=*min_element(all(cs[i]));
		forn(j,n){v[j]=cs[0][j]-u[0];for1(i,n - 1)v[j]=min(v[j],cs[i][j]-u[i]);}
		L=R=vi(n, -1);
		forn(i,n)forn(j,n)
			if(R[j]==-1&&zero(cs[i][j]-u[i]-v[j])){L[i]=j;R[j]=i;mat++;break;}
		for(;mat<n;mat++){
		    int s=0, j=0, i;
		    while(L[s] != -1)s++;
		    fill(all(dad),-1);fill(all(sn),0);
		    forn(k,n)ds[k]=cs[s][k]-u[s]-v[k];
		    for(;;){
		        j = -1;
		        forn(k,n)if(!sn[k]&&(j==-1||ds[k]<ds[j]))j=k;
		        sn[j] = 1; i = R[j];
		        if(i == -1) break;
		        forn(k,n)if(!sn[k]){
		            auto new_ds=ds[j]+cs[i][k]-u[i]-v[k];
		            if(ds[k] > new_ds){ds[k]=new_ds;dad[k]=j;}
		        }
		    }
		    forn(k,n)if(k!=j&&sn[k]){auto w=ds[k]-ds[j];v[k]+=w,u[R[k]]-=w;}
		    u[s] += ds[j];
		    while(dad[j]>=0){int d = dad[j];R[j]=R[d];L[R[j]]=j;j=d;}
		    R[j]=s;L[s]=j;
		}
		ll value=0;forn(i,n)value+=cs[i][L[i]];
		return value;
	}
};

struct pt{
    int x, y;
    pt(){}
    pt(int x, int y): x(x), y(y){}
    ll dst(pt p){return abs(x - p.x) + abs(y - p.y); }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.precision(21);
    int n, m;
    cin >> m >> n;
    vector<pt> crs(n), wn(m);
    forn(j, m)cin >> wn[j].x >> wn[j].y;
    forn(i, n)cin >> crs[i].x >> crs[i].y;
    pt rst = pt();
    cin >> rst.x >> rst.y;
    int N = n + m - 1;
    int M = m;
    Hungarian hug = Hungarian(N, M);

    forn(i, n){
        forn(j, m){
            hug.set(i, j, crs[i].dst(wn[j]));
        }
    }
    ll ans = 0;
    forn(j, m){
        ans += rst.dst(wn[j]);
    }
    forn(i, m - 1){
        forn(j, m){
            hug.set(i + n, j, rst.dst(wn[j]));
        }
    }
    ans += hug.assign();
    cout << ans << el;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3564kb

input:

1 1
-324 -832
-324 -832
-324 -832

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3468kb

input:

2 2
1 0
0 -1
-1 1
2 -1
0 0

output:

5

result:

ok single line: '5'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3564kb

input:

1 1
597 546
-353 -842
597 546

output:

2338

result:

ok single line: '2338'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3460kb

input:

1 1
-224 757
122 562
122 562

output:

1082

result:

ok single line: '1082'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3520kb

input:

3 1
-941 122
-941 122
-941 122
-763 292
976 473

output:

11688

result:

ok single line: '11688'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

1 3
-895 -38
182 -115
182 -115
182 -115
564 -943

output:

3518

result:

ok single line: '3518'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3472kb

input:

3 3
624 -328
656 -272
435 -210
-396 460
-961 -758
-741 -263
575 -316

output:

1847

result:

ok single line: '1847'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3428kb

input:

3 3
-322 -245
479 -822
-653 681
461 705
480 706
554 690
543 682

output:

9016

result:

ok single line: '9016'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3528kb

input:

1 1
-19 106
-407 -746
-837 935

output:

2887

result:

ok single line: '2887'

Test #10:

score: 0
Accepted
time: 3ms
memory: 10932kb

input:

1 1000
458 551
-136 -439
934 816
-424 -347
329 296
-322 -757
-668 -497
409 -928
1000 -486
-924 -233
716 50
-635 645
931 -594
-434 -678
-124 -264
316 277
-946 235
929 132
485 -639
183 -466
169 827
615 316
534 330
-901 783
-117 -503
-97 -182
-115 -460
764 -703
324 -155
-300 599
986 2
-329 -203
399 953...

output:

1639

result:

ok single line: '1639'

Test #11:

score: 0
Accepted
time: 571ms
memory: 10948kb

input:

1000 1
-129 473
135 -254
476 -458
72 -905
-510 -153
-780 116
-548 -129
-671 892
-697 64
-388 699
-480 93
244 -156
326 604
250 319
986 991
-208 525
-132 889
-657 -990
42 -632
-268 -328
991 -826
-172 211
535 359
514 -908
-381 -864
598 622
195 973
-331 -566
-353 -768
-139 857
603 -852
674 -429
700 248
...

output:

3067457

result:

ok single line: '3067457'

Test #12:

score: 0
Accepted
time: 1259ms
memory: 34788kb

input:

1000 1000
-184 402
590 -350
-240 949
-28 -995
901 -709
228 -865
-771 861
-545 -734
643 -978
499 199
-817 358
211 877
143 -220
-568 932
-724 -357
-527 305
347 -634
286 848
184 -706
-821 -793
-907 341
-594 -626
-850 971
-969 933
191 -559
-511 894
-505 36
75 -988
749 409
800 113
-545 -771
376 -983
549 ...

output:

1436567

result:

ok single line: '1436567'

Test #13:

score: 0
Accepted
time: 7ms
memory: 10904kb

input:

1000 1
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
100...

output:

8000000

result:

ok single line: '8000000'

Test #14:

score: 0
Accepted
time: 379ms
memory: 14040kb

input:

653 519
-631 -589
781 -909
409 -164
797 -765
271 -115
-622 -575
322 -863
160 513
-931 451
-163 852
347 -860
-480 -567
-460 477
-840 -217
478 -744
367 897
-840 736
627 59
344 -577
622 -305
-820 309
-680 -575
660 658
271 880
-550 811
-878 668
-886 851
797 400
-983 168
-746 -687
902 688
312 -386
800 -2...

output:

1105820

result:

ok single line: '1105820'

Test #15:

score: 0
Accepted
time: 587ms
memory: 25304kb

input:

721 952
-771 387
-22 -756
717 -683
169 -761
-481 -176
-32 212
559 501
-708 863
-647 804
-845 -822
-307 -623
201 129
954 -820
788 456
68 -793
-979 887
680 655
-229 843
-292 -503
-880 23
462 53
-207 780
-787 113
-844 -781
-490 182
-146 -673
274 813
-702 -927
500 94
-23 896
-872 -412
-103 121
609 -841
...

output:

1090958

result:

ok single line: '1090958'

Test #16:

score: 0
Accepted
time: 180ms
memory: 10144kb

input:

488 461
232 -232
314 -605
-121 -40
870 -163
750 711
-467 -658
-823 -364
-93 289
-508 -387
-928 -246
698 33
760 -839
-29 934
307 -504
-762 -507
693 772
420 272
-557 251
1 505
149 628
-460 798
829 619
488 967
960 -910
320 -218
610 648
-38 -751
-760 370
184 -789
222 579
-728 242
151 -254
-376 -763
819 ...

output:

883252

result:

ok single line: '883252'