QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#297402#7857. (-1,1)-Sumpleteucup-team870#TL 15ms18764kbC++203.1kb2024-01-04 13:19:502024-01-04 13:19:50

Judging History

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

  • [2024-01-04 13:19:50]
  • 评测
  • 测评结果:TL
  • 用时:15ms
  • 内存:18764kb
  • [2024-01-04 13:19:50]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define per(i,r,l) for(int i=r; i>=l; i--)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

const int N = 10010;

struct edge {
    int to, next, flow;
} ed[33000010];

int s, t, deep[N], head[N], cur[N], sz=-1, row[N], col[N];
char a[4040][4040];
bool ksj[4040][4040];

char tmp[N];

void addEdge(int from, int to, int flow) {
    sz++;
    ed[sz].to = to;
    ed[sz].next = head[from];
    ed[sz].flow = flow;
    head[from] = sz;
}

void add(int u, int v, int f) {
    addEdge(u, v, f);
    addEdge(v, u, 0);
}

bool bfs() {
    queue <int> q;
    q.push(s);
    memset(deep, 0, sizeof(deep));
    deep[s] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != -1; i = ed[i].next) {
            int v = ed[i].to;
            if (deep[v] == 0 && ed[i].flow > 0) {
                deep[v] = deep[u] + 1;
                q.push(v);
                if (v == t) return true;
            }
        }
    }
    return false;
}

int dfs(int u, int flow) {
    if (u == t) return flow;
    int rest = flow;
    for (int i = cur[u]; i != -1; i = ed[i].next) {
        int v = ed[i].to;
        if (deep[v] == deep[u] + 1 && ed[i].flow > 0 && rest) {
            int now = dfs(v, min(ed[i].flow, rest));
            if (!now) deep[v] = 0;
            rest -= now;
            ed[i].flow -= now;
            ed[i^1].flow += now;
            if (ed[i].flow) cur[u] = i;
            if (rest == 0) break;
        }
    }
    if (rest == flow) deep[u] = -1;
    return flow - rest;
}

int dinic() {
    int flow = 0;
    while (bfs()) {
        rep (i, 1, t) cur[i] = head[i];
        flow += dfs(s, 1e9);
    }
    return flow;
}

int main() {
    memset(head, -1, sizeof(head));
    int n; scanf("%d", &n);
    rep (i, 1, n) {
        scanf("%s", tmp+1);
        rep (j, 1, n) {
            if (tmp[j] == '+') a[i][j] = 1;
        }
    }
    rep (i, 1, n) {
        scanf("%d", &row[i]);
    }
    rep (i, 1, n) {
        scanf("%d", &col[i]);
    }
    rep (i, 1, n) {
        rep (j, 1, n) {
            if (!a[i][j]) {
                row[i]++, col[j]++;
                ksj[i][j] = 1;
            }
            add(i, j+n, 1);
        }
    }
    s = 2*n+1, t = s+1;
    int sumS = 0, sumT= 0 ;
    rep (i, 1, n) {
        add(s, i, row[i]);
        sumS += row[i];
        sumT += col[i];
        add(i+n, t, col[i]);
    }

    int flow = dinic();
    if (sumS == sumT && flow == sumS) {
        puts("Yes");
        rep (u, 1, n) {
            for (int i = head[u]; i != -1; i = ed[i].next) {
                int v = ed[i].to;
                if (v != s) {
                    if (ed[i].flow == 0) ksj[u][v-n] ^= 1;
                }
            }
        }
        rep (i, 1, n) {
            rep (j, 1, n) {
                printf("%d", ksj[i][j]);
            }
            cout <<'\n';
        }
    } else {
        puts("No");
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 8132kb

input:

3
+-+
-++
+-+
1 1 1
1 -1 3

output:

Yes
111
001
001

result:

ok n=3

Test #2:

score: 0
Accepted
time: 1ms
memory: 7856kb

input:

3
---
-++
+++
-2 -1 0
-2 -1 0

output:

Yes
110
100
000

result:

ok n=3

Test #3:

score: 0
Accepted
time: 0ms
memory: 7748kb

input:

3
+-+
-++
++-
1 0 2
2 2 -1

output:

No

result:

ok n=3

Test #4:

score: 0
Accepted
time: 1ms
memory: 5692kb

input:

1
-
-1
1

output:

No

result:

ok n=1

Test #5:

score: 0
Accepted
time: 1ms
memory: 5824kb

input:

1
-
0
0

output:

Yes
0

result:

ok n=1

Test #6:

score: 0
Accepted
time: 1ms
memory: 9992kb

input:

20
+-------+-----+++-++
-+-++++----++-++-++-
-+++--+---+--+-++---
-+++-+--+----++---+-
+++-+-++++++-+-+---+
-++-----+----++++++-
+-++--+++++-++-+----
+-+----+---+-+++--+-
+++++-+++++----+--+-
------++++---+--++--
++++--------++++--+-
-+-+-++++-+-++-++--+
---+-++---+-++-++---
+-++++-++----+-+++--
+-+...

output:

Yes
10000011011111011011
01011111111001010110
01110011110110100000
01110101111110011101
11101010100010110001
10100000111101001001
01001011100111100111
01010001001101000111
00000100110000000111
11111100110001011001
00001111111111100111
10101000001011011100
11101110001011011100
01000010100001011100
01...

result:

ok n=20

Test #7:

score: 0
Accepted
time: 2ms
memory: 10272kb

input:

100
++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++
-++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++
--+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...

output:

Yes
1111010100111111010010100101011000001000111011010110101110000000101100101100100111110110100010010011
0110011010111101000110010101010101010101010010011100010010000010000010110110101111110010111011101111
0010001101100110111000111101101001111110111001001000011111111010011111001100101011100010011101...

result:

ok n=100

Test #8:

score: 0
Accepted
time: 15ms
memory: 18764kb

input:

500
--+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...

output:

Yes
00101010110000011100101110100010100000011111001100101101100011001001001011001101110011001111001101110010011011111010111001000010000000111001001101000010111100100010001110110001011001001100000001000110111011101011100101011010001001111100010010001010011000000101001000111001000100111101100011110000...

result:

ok n=500

Test #9:

score: -100
Time Limit Exceeded

input:

4000
-++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...

output:

Yes
01101010100101111000101100000011000101110011100111111100010110111111100001000111011001100010110010000100010011010101000001010001001000100011101111010000011001101101011010011101001001010000111011111011101010001110110100101001100111100010100110001010001000111010000101001100010000010100100001111101...

result: