QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#431838 | #3179. Cordon Bleu | juancs | AC ✓ | 1259ms | 34788kb | C++20 | 2.8kb | 2024-06-06 10:07:14 | 2024-06-06 10:07:14 |
Judging History
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'