QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#134760 | #5371. Matrix | masterhuang | 30 | 1ms | 3632kb | C++23 | 2.3kb | 2023-08-04 21:17:04 | 2023-08-04 21:17:07 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=205,M=5505;
int TOT,n,m,a[N][N],b[N],c[N],tot=1,head[N],_head[N],d[N],S,T,nx,ny,tt,as[N][N];
struct edge{int to,nex,w;}e[M<<1];
inline void add(int u,int v,int w)
{
e[++tot]={v,head[u],w};head[u]=tot;
e[++tot]={u,head[v],0};head[v]=tot;
}
inline bool bfs()
{
queue<int>q;memset(d,0,sizeof(d));d[S]=1;q.push(S);
while(!q.empty())
{
int t=q.front();q.pop();
for(int i=head[t];i;i=e[i].nex)
{
int to=e[i].to;
if(!d[to]&&e[i].w>0) d[to]=d[t]+1,q.push(to);
}
}return d[T];
}
int dfs(int x,int flow)
{
if(x==T) return flow;int old=flow;
for(int &i=_head[x];i;i=e[i].nex)
{
int to=e[i].to;
if(d[to]==d[x]+1&&e[i].w>0)
{
int nw=dfs(to,min(e[i].w,flow));flow-=nw;
e[i].w-=nw,e[i^1].w+=nw;
if(!flow) break;
}
}return (flow==old)&&(d[x]=0),old-flow;
}
inline int dinic(){int ans=0;while(bfs()) memcpy(_head,head,sizeof(head)),ans+=dfs(S,1e9);return ans;}
inline bool chk()
{
// for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(nx==-1||a[i][j]<a[nx][ny]) nx=i,ny=j;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[i][j]) return nx=i,ny=j,1;return 0;
}
inline void sol()
{
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[i][j]<0) return cout<<"-1\n",void();
for(int i=1,s=0;i<=n;i++,s=0){for(int j=1;j<=n;j++) s+=a[i][j];b[i]=s;}
for(int i=1,s=0;i<=n;i++,s=0){for(int j=1;j<=n;j++) s+=a[j][i];b[i+n]=s;}
for(int i=1;i<2*n;i++) if(b[i]^b[i+1]) return cout<<"-1\n",void();S=0;T=2*n+1;tt=0;
while(chk())
{
tot=1;memset(head,0,sizeof(head));
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[i][j]) add(i,n+j,1);
for(int i=1;i<=n;i++) add(S,i,1),add(i+n,T,1);int ans=dinic();assert(ans==n);
for(int i=1;i<=n;i++) for(int j=head[i];j;j=e[j].nex) if(!e[j].w){c[i]=e[j].to-n;break;}
int mn=1e9;for(int i=1;i<=n;i++) mn=min(mn,a[i][c[i]]);as[++tt][0]=mn;
for(int i=1;i<=n;i++) a[i][c[i]]-=mn,as[tt][i]=c[i];
}cout<<tt<<"\n";
for(int i=1;i<=tt;i++,cout<<"\n") for(int j=0;j<=n;j++) cout<<as[i][j]<<" ";
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>TOT;
while(TOT--){cin>>n;for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];sol();}
return 0;
}
详细
Subtask #1:
score: 30
Accepted
Test #1:
score: 30
Accepted
time: 1ms
memory: 3568kb
input:
10 5 41 18467 6334 26500 2995 19169 15724 11478 29358 -21392 26962 24464 5705 28145 -30939 23281 16827 9961 491 3777 -15116 -21145 20859 -30157 99896 5 4827 5436 32391 14604 1869 3902 153 292 12382 42398 17421 18716 19718 19895 -16623 5447 21726 14771 11538 5645 27530 13096 -8045 708 25838 5 41879 4...
output:
-1 -1 17 8106 1 2 3 4 5 23247 1 2 3 5 4 10526 1 3 2 5 4 10350 5 3 2 1 4 5684 2 3 1 5 4 2380 5 2 1 3 4 6290 5 2 1 4 3 29460 2 1 5 4 3 2974 5 4 1 2 3 16557 5 4 1 3 2 15455 4 1 5 3 2 27014 3 4 5 1 2 7101 4 3 5 1 2 3550 4 3 5 2 1 7367 2 5 4 3 1 6233 3 5 4 2 1 10323 5 3 4 2 1 -1 -1 -1 -1...
result:
ok good solution (10 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
10 5 59894 57729 53053 37667 58044 49556 41863 58059 44760 72149 49555 42862 54181 52697 67092 55846 40495 51765 66802 51479 51536 83438 49329 64461 17623 5 6224 11008 5844 32609 13458 14989 32702 3195 20485 -2228 3093 14343 30523 1587 19597 29314 9503 7448 25200 -2322 15523 1587 22133 -10738 40638 ...
output:
17 17623 1 2 3 4 5 24240 1 2 3 5 4 12318 2 1 3 5 4 14921 1 3 2 5 4 12982 2 1 5 3 4 24256 2 1 5 4 3 8173 2 5 1 4 3 3110 1 5 2 4 3 13790 4 5 2 1 3 13640 5 3 1 4 2 27742 5 4 1 3 2 17018 3 4 5 1 2 12836 4 3 5 1 2 12202 3 5 4 1 2 11041 4 5 2 3 1 23833 3 5 4 2 1 16662 5 3 4 2 1 -1 17 5281...
result:
ok good solution (10 test cases)
Test #3:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
10 5 10202 3625 26477 4414 17773 9314 25824 29334 25874 -27855 24372 20159 11833 28070 -21943 7487 28297 7518 8177 11012 11116 -15414 -12671 -4044 83504 5 80335 81240 95764 92557 91633 81674 87052 107785 86199 78819 83374 82671 109099 81197 85188 80115 80496 89595 108544 82779 116031 110070 39286 73...
output:
-1 17 80335 1 2 3 4 5 6717 5 2 3 4 1 21492 2 1 3 4 5 1283 2 1 4 3 5 555 2 1 3 5 4 72477 5 3 2 1 4 39286 2 1 4 5 3 7638 5 3 4 1 2 27670 4 3 1 5 2 15268 3 1 4 5 2 4801 5 4 1 3 2 3790 4 1 5 3 2 18624 2 4 5 3 1 50903 4 5 1 3 2 62774 3 4 5 2 1 10194 4 5 2 3 1 17722 3 5 4 2 1 -1 -1 -1 17 ...
result:
ok good solution (10 test cases)
Test #4:
score: 0
Accepted
time: 1ms
memory: 3500kb
input:
10 5 22335 24708 38072 45631 16687 27829 32738 19360 45510 21996 22430 32748 37233 30145 24877 38308 18739 18383 18259 53744 36531 38500 34385 7888 30129 5 44671 57452 39279 47542 49809 36827 56746 58358 41115 45707 57345 54779 56063 52429 18137 37825 52474 36230 66538 45686 62085 17302 48823 31129 ...
output:
17 18259 1 2 3 4 5 4076 1 2 4 3 5 10403 5 2 4 3 1 3904 2 1 4 3 5 6284 5 3 4 2 1 3890 4 3 1 2 5 7888 2 1 3 5 4 5478 2 1 4 5 3 10559 4 1 2 5 3 19844 3 4 2 5 1 7438 2 4 1 5 3 2345 4 5 2 1 3 2537 3 4 1 5 2 8565 4 5 1 2 3 15691 3 4 5 1 2 9186 4 3 5 1 2 11086 4 5 3 1 2 17 44671 1 2 3 4 5 ...
result:
ok good solution (10 test cases)
Test #5:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
10 5 14423 3527 11600 26969 1588 14015 5565 28 21543 16956 25347 2088 2943 12637 15092 22409 26463 5049 4681 -495 -18087 20464 38487 -7723 24966 5 608 32060 21221 1758 18035 29954 20888 14146 690 8004 7949 12843 21430 25620 5840 748 27067 4536 20783 20548 34423 -19176 12349 24831 21255 5 64025 55878...
output:
-1 -1 17 53784 1 2 3 4 5 10241 1 3 2 4 5 5840 5 3 2 4 1 10804 5 2 4 3 1 37996 2 1 4 3 5 52551 5 3 2 1 4 131 4 3 2 5 1 4843 3 1 2 5 4 4538 3 5 1 2 4 14995 2 1 4 5 3 2887 2 4 1 5 3 1564 3 4 1 5 2 2230 4 1 5 2 3 28141 3 4 5 2 1 46657 4 5 1 2 3 19607 3 4 5 1 2 25451 4 5 1 3 2 -1 -1 -1 1...
result:
ok good solution (10 test cases)
Test #6:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
10 5 18115 1679 17110 25898 28 23073 788 23977 18132 -3140 29956 28689 26113 10008 -31936 12941 15790 1723 21363 11013 -21255 15884 -6093 -12571 86865 5 127174 109596 107467 104281 105705 124370 103467 113729 125263 87394 128549 116691 134564 123221 51198 112072 118025 131046 104994 88086 62058 1064...
output:
-1 17 103467 1 2 3 4 5 1527 2 1 3 4 5 108069 2 1 4 3 5 14774 5 1 4 3 2 378 1 5 4 3 2 7825 1 4 2 3 5 952 1 4 3 2 5 14552 1 5 3 2 4 14066 4 5 3 2 1 81912 5 3 2 1 4 9019 5 4 2 1 3 17935 3 4 2 5 1 70151 3 4 1 5 2 19381 3 4 5 2 1 58398 4 5 1 2 3 21141 4 3 5 1 2 10676 4 3 5 2 1 -1 -1 -1 1...
result:
ok good solution (10 test cases)
Test #7:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
10 5 18337 1278 12393 7636 25608 30714 28164 31591 19949 -45166 19135 2505 13337 10004 20271 16337 2623 28664 9970 7658 -19271 30682 -20733 17693 56881 5 118623 106427 108494 117715 101283 127994 107536 109218 123168 84626 127738 106914 105591 113982 98317 128516 118161 100285 131953 73627 49671 113...
output:
-1 17 105591 1 2 3 4 5 13032 1 3 2 4 5 13330 5 3 2 4 1 1945 5 2 4 3 1 76066 2 1 4 3 5 65724 5 3 2 1 4 30361 2 1 4 5 3 5610 5 1 4 2 3 14674 5 4 2 1 3 154 4 1 2 5 3 43112 3 4 1 5 2 15803 4 1 5 2 3 34396 3 4 5 2 1 62352 4 5 1 2 3 30986 3 4 5 1 2 22274 4 5 1 3 2 17132 4 3 5 1 2 17 79455...
result:
ok good solution (10 test cases)
Test #8:
score: 0
Accepted
time: 1ms
memory: 3504kb
input:
10 5 32179 16595 20169 2327 25783 12042 31310 28182 11058 14461 7926 9487 1670 32528 45442 5651 2258 7213 9860 72071 39255 37403 39819 41280 -60704 5 58360 64228 60090 62746 84076 74052 61459 76336 59121 58532 70485 80483 66556 57499 54477 64875 78368 84232 74216 27809 61728 44962 42286 75918 104606...
output:
-1 17 58360 1 2 3 4 5 3099 5 2 3 4 1 5097 2 1 3 4 5 7660 5 3 2 4 1 41149 2 1 4 3 5 64875 5 3 2 1 4 3801 4 3 2 5 1 4147 3 1 2 5 4 6896 3 5 1 2 4 16350 2 1 4 5 3 1632 2 4 1 5 3 8442 5 4 1 2 3 1879 3 4 1 5 2 7309 4 1 5 2 3 47168 3 4 5 2 1 8553 4 5 1 2 3 43083 4 5 1 3 2 -1 -1 -1 17 2210...
result:
ok good solution (10 test cases)
Test #9:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
10 5 27577 12750 14007 23729 29929 24081 2995 2678 24676 53562 27753 20899 11784 15565 31991 3093 13608 6172 11243 73876 25488 57740 73351 32779 -81366 5 10168 5055 11191 5973 15469 8922 6748 5651 10986 15549 2144 16446 31577 26517 -28828 14629 29916 5874 15791 -18354 11993 -10309 -6437 -11411 64020...
output:
-1 -1 17 33292 1 2 3 4 5 248 5 2 3 4 1 18463 5 2 4 3 1 12516 2 1 4 3 5 1093 2 1 3 5 4 33697 5 3 2 1 4 2794 2 3 1 5 4 25393 2 1 4 5 3 7097 2 4 1 5 3 2918 5 4 1 2 3 13093 4 1 5 2 3 26090 3 4 5 2 1 2169 2 4 5 1 3 8147 3 4 5 1 2 4777 2 4 5 3 1 12573 4 5 1 3 2 9295 4 3 5 1 2 -1 -1 17 139...
result:
ok good solution (10 test cases)
Test #10:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
10 5 52175 34573 47184 34242 48829 39726 48464 56486 42655 29672 58676 54948 45757 42343 15279 45044 49757 42978 51268 27956 21382 29261 24598 46495 95267 5 115939 94609 88842 92104 98792 89855 95791 96911 101968 105761 111710 103031 92884 106351 76310 116598 114955 95676 118795 44262 56184 81900 11...
output:
17 45757 1 2 3 4 5 5511 1 3 2 4 5 907 1 2 4 3 5 1800 5 2 4 3 1 34573 2 1 4 3 5 5063 5 1 4 3 2 635 5 4 2 3 1 8519 3 4 1 2 5 41331 5 3 2 1 4 7471 4 3 2 5 1 2173 4 3 1 5 2 5164 3 5 1 2 4 18312 3 4 1 5 2 90 4 1 5 2 3 11476 3 4 5 2 1 24508 4 5 1 2 3 3713 3 4 5 1 2 17 92884 1 2 3 4 5 230...
result:
ok good solution (10 test cases)
Subtask #2:
score: 0
Dangerous Syscalls
Dependency #1:
100%
Accepted
Test #11:
score: 0
Dangerous Syscalls
input:
10 30 3303373 3309415 3289962 3309855 3312694 3291644 3309691 3294908 3296047 3312358 3320956 3313078 3317639 3306313 3317589 3316838 3308551 3311957 3312323 3293346 3313147 3293374 3301630 3308503 3311855 3315564 3317401 3290456 3301303 3309428 3308147 3304361 3303158 3313330 3307333 3299369 330747...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%