QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#67734 | #4786. Balance | A_zjzj | WA | 3ms | 3560kb | C++14 | 1.7kb | 2022-12-11 16:30:49 | 2022-12-11 16:30:53 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;using ll=long long;const int N=55,V=N*2,E=N*N*2,INF=1e9;
int n,s,t,kk=1,a[N][N],p[N],dis[V],pre[V],mn[V],head[V],in[N],x[N],y[N];vector<pair<int,int> >A[N];
struct edges{int to,c,w,nex;}edge[E];
void add(int u,int v,int c,int w){
edge[++kk]={v,c,w,head[u]};head[u]=kk;
edge[++kk]={u,0,-w,head[v]};head[v]=kk;
}
void add(int u,int v,int w){A[u].push_back({v,w});in[v]++;}
bool bfs(){
queue<int>q;q.push(s);memset(dis,-0x3f,sizeof dis);dis[s]=0;mn[s]=INF;for(int u;!q.empty();q.pop()){
u=q.front();for(int i=head[u],v;v=edge[i].to,i;i=edge[i].nex)if(edge[i].c&&dis[v]<dis[u]+edge[i].w)
pre[v]=i,dis[v]=dis[u]+edge[i].w,mn[v]=min(mn[u],edge[i].c),q.push(v);
}return dis[t]>-INF;
}
int EK(){
int sum=0;for(;bfs();){
for(int u=t;u^s;u=edge[pre[u]^1].to){
edge[pre[u]].c-=mn[t];edge[pre[u]^1].c+=mn[t];
sum+=edge[pre[u]].w*mn[t];
}
}return sum;
}
void topo(){
queue<int>q;for(int i=1;i<=n;i++)if(!in[i])q.push(i);for(int u;!q.empty();q.pop()){
u=q.front();for(auto [v,w]:A[u])if(x[v]=max(x[v],x[u]+w+1),!--in[v])q.push(v);
}
}
int main(){
cin>>n;t=n+n+1;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j],add(i,j+n,1,a[i][j]);
for(int i=1;i<=n;i++)add(s,i,1,0),add(i+n,t,1,0);cout<<EK()*n<<endl;
for(int u=1;u<=n;u++)for(int i=head[u],v;v=edge[i].to,i;i=edge[i].nex)if(!edge[i].c)p[v-n]=u;
// if(n==24)for(int i=1;i<=n;i++)cout<<p[i]<<"\n "[i<n];
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i^p[j]&&a[i][j]-a[p[j]][j]>0)add(p[j],i,a[i][j]-a[p[j]][j]-1);
// if(n==24)for(int i=1;i<=n;i++)cout<<in[i]<<"\n "[i<n];
topo();for(int i=1;i<=n;i++)y[i]=a[p[i]][i]-x[p[i]];
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cout<<x[i]+y[j]<<"\n "[j<n];return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3356kb
input:
4 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
output:
16 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
result:
ok correct plan, good job!
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 3560kb
input:
24 20594 15420 1258 6283 18795 7007 20323 16605 27476 270 2082 5286 32911 30847 17237 14187 9258 26749 27575 8042 2690 25493 23540 30506 15252 21600 26878 32384 22641 12550 29190 28725 33837 7235 6316 1318 10773 4177 6535 33628 31431 19567 25294 22712 18861 16725 25214 12950 29777 22466 16743 2033 3...
output:
18759816 28753 28333 34991 29080 34858 31880 31797 27534 32646 29833 32699 28667 32911 32784 31513 33224 31100 30928 31185 26141 28449 32196 26090 34098 29944 29524 36182 30271 36049 33071 32988 28725 33837 31024 33890 29858 34102 33975 32704 34415 32291 32119 32376 27332 29640 33387 27281 35289 297...
result:
wrong answer condition B[2][4] >= A[2][4] failed