QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#343381 | #7857. (-1,1)-Sumplete | hl666 | TL | 30ms | 12572kb | C++17 | 2.7kb | 2024-03-02 14:52:40 | 2024-03-02 14:52:41 |
Judging History
answer
#include <bits/stdc++.h>
namespace NetWork_Flow
{
using std::queue;
const int INF=1e9;
const int NN=8005,MM=int(1.5 * 4000*4000)+5;
struct edge
{
int to,nxt,v;
}e[MM<<1]; int cnt=1,head[NN],cur[NN],dep[NN],s,t;
inline int addedge(int x,int y,int z)
{
// std::cerr << "addedge(" << x << ", " << y << ", " << z << ")\n";
e[++cnt]=(edge){y,head[x],z}; head[x]=cnt;
e[++cnt]=(edge){x,head[y],0}; head[y]=cnt;
return cnt - 1;
}
#define to e[i].to
inline bool BFS(void)
{
memset(dep,0,(t+1)*sizeof(int)); dep[s]=1;
queue <int> q; q.push(s);
while (!q.empty())
{
int now=q.front(); q.pop();
for (int i=head[now];i;i=e[i].nxt)
if (e[i].v&&!dep[to]) dep[to]=dep[now]+1,q.push(to);
}
return dep[t];
}
inline int DFS(int now,int tar,int dis)
{
if (now==tar) return dis; int ret=0;
for (int& i=cur[now];i&&dis;i=e[i].nxt)
if (e[i].v&&dep[to]==dep[now]+1)
{
int dist=DFS(to,tar,std::min(dis,e[i].v));
if (!dist) dep[to]=INF;
dis-=dist; ret+=dist; e[i].v-=dist; e[i^1].v+=dist;
if (!dis) return ret;
}
if (!ret) dep[now]=0; return ret;
}
#undef to
inline int Dinic(int ret=0)
{
while (BFS()) memcpy(cur,head,t+1<<2),ret+=DFS(s,t,INF); return ret;
}
};
int n;
int ed[4005][4005];
int main() {
std::ios::sync_with_stdio(false);
std::cin >> n;
using NetWork_Flow::s;
using NetWork_Flow::t;
using NetWork_Flow::addedge;
s = 2 * n, t = 2 * n + 1;
for(int i = 0; i < n; ++i) {
using NetWork_Flow::addedge;
std::string s; std::cin >> s;
for(int j = 0; j < n; ++j){
if(s[j] == '+')
ed[i][j] = addedge(i, j + n, 1);
else
ed[i][j] = addedge(j + n, i, 1);
}
}
int rs = 0, cs = 0;
for(int i = 0, r; i < n; ++i) {
std::cin >> r;
if(r > 0) rs += r, addedge(s, i, r);
if(r < 0) cs -= r, addedge(i, t, -r);
}
for(int i = 0, c; i < n; ++i) {
std::cin >> c;
if(c > 0) cs += c, addedge(i + n, t, c);
if(c < 0) rs -= c, addedge(s, i + n, -c);
}
if(rs != cs) return std::cout << "No\n", 0;
int max_flow = NetWork_Flow::Dinic();
if(max_flow != rs) return std::cout << "No\n", 0;
std::cout << "Yes\n";
for(int i = 0; i < n; ++i) {
using NetWork_Flow::e;
for(int j = 0; j < n; ++j)
std::cout << char('0' + (e[ed[i][j]].v == 0));
std::cout << char(10);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3564kb
input:
3 +-+ -++ +-+ 1 1 1 1 -1 3
output:
Yes 001 001 111
result:
ok n=3
Test #2:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
3 --- -++ +++ -2 -1 0 -2 -1 0
output:
Yes 110 100 000
result:
ok n=3
Test #3:
score: 0
Accepted
time: 1ms
memory: 3920kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
No
result:
ok n=3
Test #4:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
1 - -1 1
output:
No
result:
ok n=1
Test #5:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
1 - 0 0
output:
Yes 0
result:
ok n=1
Test #6:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
20 +-------+-----+++-++ -+-++++----++-++-++- -+++--+---+--+-++--- -+++-+--+----++---+- +++-+-++++++-+-+---+ -++-----+----++++++- +-++--+++++-++-+---- +-+----+---+-+++--+- +++++-+++++----+--+- ------++++---+--++-- ++++--------++++--+- -+-+-++++-+-++-++--+ ---+-++---+-++-++--- +-++++-++----+-+++-- +-+...
output:
Yes 00000000010000000100 00000000000010100010 00000000010000000100 00000011010000000100 00100000100101010001 00000000010000000000 00000000000101000101 00000000000000000001 00000000000000000000 00000100001100000001 00000001011100000101 00000000000101001000 10000000000001011000 00000000000001011000 00...
result:
ok n=20
Test #7:
score: 0
Accepted
time: 1ms
memory: 4332kb
input:
100 ++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++ -++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++ --+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...
output:
Yes 1111010100111111010010011010100010100000000000000000000000000000000000000000000011110110100010010011 0110011010111101000110101010100010100000000000000000000000000000000000000000101111110010111011101111 0010001101100110111000000010010010000000000000000000000000000000000000000000001011100010011101...
result:
ok n=100
Test #8:
score: 0
Accepted
time: 30ms
memory: 12572kb
input:
500 --+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...
output:
Yes 11010101001111100011010001011101011111110001100000010110011010100001000011001101110011001111001101110010011011111010111001000010000000111001001101000010111100100010001110110001010001001100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok n=500
Test #9:
score: -100
Time Limit Exceeded
input:
4000 -++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...