QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#343381#7857. (-1,1)-Sumpletehl666TL 30ms12572kbC++172.7kb2024-03-02 14:52:402024-03-02 14:52:41

Judging History

你现在查看的是最新测评结果

  • [2024-03-02 14:52:41]
  • 评测
  • 测评结果:TL
  • 用时:30ms
  • 内存:12572kb
  • [2024-03-02 14:52:40]
  • 提交

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
-++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...

output:


result: