QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#289756 | #7857. (-1,1)-Sumplete | ucup-team139# | TL | 1535ms | 405728kb | C++23 | 3.6kb | 2023-12-23 23:02:22 | 2023-12-23 23:02:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using pi = pair<int,int>;
#define sz(x) int((x).size())
template<class F> struct Dinic {
struct Edge { int to, rev; F cap; };
int N; vector<vector<Edge>> adj;
void init(int _N) { N = _N; adj.resize(N); } //0-based
pi ae(int a, int b, F cap, F rcap = 0) {
assert(min(cap,rcap) >= 0); // saved me > once
adj[a].push_back({b,sz(adj[b]),cap});
adj[b].push_back({a,sz(adj[a])-1,rcap});
return {a,sz(adj[a])-1};
}
F edgeFlow(pi loc) { // get flow along original edge
const Edge& e = adj.at(loc.first).at(loc.second);
return adj.at(e.to).at(e.rev).cap;
}
vector<int> lev, ptr;
bool bfs(int s,int t){//level=shortest dist from source
lev = ptr = vector<int>(N);
lev[s] = 1; queue<int> q({s});
while (sz(q)) { int u = q.front(); q.pop();
for(auto& e: adj[u]) if (e.cap && !lev[e.to]) {
q.push(e.to), lev[e.to] = lev[u]+1;
if (e.to == t) return 1;
}
}
return 0;
}
F dfs(int v, int t, F flo) {
if (v == t) return flo;
for (int& i = ptr[v]; i < sz(adj[v]); i++) {
Edge& e = adj[v][i];
if (lev[e.to]!=lev[v]+1||!e.cap) continue;
if (F df = dfs(e.to,t,min(flo,e.cap))) {
e.cap -= df; adj[e.to][e.rev].cap += df;
return df; } // saturated $\geq1$ one edge
}
return 0;
}
F maxFlow(int s, int t) {
F tot = 0; while (bfs(s,t)) while (F df =
dfs(s,t,numeric_limits<F>::max())) tot += df;
return tot;
}
};
void solve(int t){
int n;
cin>>n;
vector mat(n,vector(n,'.'));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>mat[i][j];
}
}
vector r(n,0),c(n,0);
for(int i=0;i<n;i++)cin>>r[i];
for(int i=0;i<n;i++)cin>>c[i];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(mat[i][j]=='-'){
r[i]++;
c[j]++;
}
}
}
long long totr=0,totc=0;
for(int i=0;i<n;i++){
if(r[i]<0 || c[i]<0){
cout<<"No\n";
return;
}
totr+=r[i];
totc+=c[i];
}
if(totr!=totc){
cout<<"No\n";
}else{
Dinic<int> ds;
int source = 2*n;
int sink = 2*n+1;
ds.init(2*n+2);
for(int i=0;i<n;i++){
ds.ae(source,i,r[i]);
ds.ae(n+i,sink,c[i]);
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
ds.ae(i,n+j,1);
}
}
if(ds.maxFlow(source,sink)!=totr){
cout<<"No\n";
}else{
vector ok(n,vector(n,false));
for(int i=0;i<n;i++){
for(auto j : ds.adj[i]){
if(j.to>=n && j.cap==0){
ok[i][j.to-n]=true;
}
}
}
cout<<"Yes\n";
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(ok[i][j]^(mat[i][j]=='-')==false){
cout<<"0";
}else{
cout<<"1";
}
}
cout<<"\n";
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)solve(i);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3456kb
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: 3572kb
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: 3440kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
No
result:
ok n=3
Test #4:
score: 0
Accepted
time: 1ms
memory: 3488kb
input:
1 - -1 1
output:
No
result:
ok n=1
Test #5:
score: 0
Accepted
time: 1ms
memory: 3524kb
input:
1 - 0 0
output:
Yes 0
result:
ok n=1
Test #6:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
20 +-------+-----+++-++ -+-++++----++-++-++- -+++--+---+--+-++--- -+++-+--+----++---+- +++-+-++++++-+-+---+ -++-----+----++++++- +-++--+++++-++-+---- +-+----+---+-+++--+- +++++-+++++----+--+- ------++++---+--++-- ++++--------++++--+- -+-+-++++-+-++-++--+ ---+-++---+-++-++--- +-++++-++----+-+++-- +-+...
output:
Yes 01111000100100101110 10101110000100100011 10000010000111101100 10010100011111010111 00101011111100100100 11100001100110001001 00110010000100101101 00100000000100001101 00011000111001101101 11110000100001000011 00000011010000001101 10100000110011011010 00010001110011011000 10100010011001011100 01...
result:
ok n=20
Test #7:
score: 0
Accepted
time: 2ms
memory: 3924kb
input:
100 ++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++ -++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++ --+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...
output:
Yes 0110001011100010101101100110100111110111000101010110101110000000101100101100111111110110100010010011 0111001110100000011001010110101010101001010010011100010010000010000010110110101111110010111011101111 1011010010111011011000000001101011110001000001001000011111111010011111001100101011100010011101...
result:
ok n=100
Test #8:
score: 0
Accepted
time: 7ms
memory: 9720kb
input:
500 --+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...
output:
Yes 11010101001111100011010001011101011111110001100111101001100101011110111100110010001100110000110010010010011011111010111001000010000000111001001101000010111100100010001110110001011001001100000001000110111011101011100101011010001001111100010010001010011000000101001000111001000100111101100011110000...
result:
ok n=500
Test #9:
score: 0
Accepted
time: 1144ms
memory: 405668kb
input:
4000 -++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...
output:
Yes 10010101011010000111010011111100111010001100011000000011101001000000011110111000100110011101001101111011101011010101000001010001101100100011101111010000011001101100011010011101001001010110111001100011101010001110110101101011100011100010100110001010001001110010000101001100010000010100100001011101...
result:
ok n=4000
Test #10:
score: 0
Accepted
time: 1022ms
memory: 405704kb
input:
4000 +---+--++-+--++-+-++--+++--++--+++-+-+-+--++++++-++-+-+++-+---++++-+-+++----++-+---++--++--+++-----++---++-+--++++----++--++--+-+-++--+--+++++-+---+++-+++--++++-++-+++++++----+++-----+--++-+++-++-++-+++-+--++++++-+--++--+-+---++--------+-+--++----+-++-+-++---+--++--+-+--+-+++-+--+--++++-++----+...
output:
Yes 01110110010110010100110001100110001010101100000010010100010111000010100011110010111001100110001111100111001011000011110011001101010011011000001011100010001100001001000000011110001111101100100010010010001011000000101100110101110011111111010110011111011010110001001100101001011101001001111011000010...
result:
ok n=4000
Test #11:
score: 0
Accepted
time: 1313ms
memory: 405668kb
input:
4000 -+--+------+--+++-++-----++--+-++-++-++-+-+-++++++--++--+-++-+-+++---++-+-+++++-++++++-+-++-++-++-+-++---+-+-------++-+++-++-+-++++-++-+-+-----+----+--+----++++-------++-+--+++----+++++++-+--+-+---+-+++++-+-----++-------++++--+-+-++---++++-++++-++-+++-+-++---+--+---+-++++++--++---+-++++++-+-+--...
output:
Yes 10110111111011000100111110011010010010010101000000110011010010100011100101000001000000101001001001010011101011111110010001001010000100101011111011110110111100001111111001011000111100000001011010111010000010111110011111110000110101001110000100001001000101001110110111010000001100111010000001010111...
result:
ok n=4000
Test #12:
score: 0
Accepted
time: 1117ms
memory: 405728kb
input:
4000 +-+-----++++-----++++-+-++-+----+++---++--+---+++-+-++------+-+-++++----+-++++--+-++----+-+---+--+-----+-++--++-+++---+---+++---++-+++---++++---++----+++--+---+---+++-++-+-+-+--+++--++----++-+------+++-++-++--+--+++---+-------++++-+-++--++-+--+------+++++---+---++-++++-+++-++++-+---++-++++----+...
output:
Yes 01011111000011111000010100101111000111001101110001010011111101010000111101000011010011110101110110111110100110010001110111000111001000111000011100111100011011101110001001010101100011001111001011111100010010011011000111011111110000101001100101101111110000011101110010000100010000101110010000111100...
result:
ok n=4000
Test #13:
score: 0
Accepted
time: 1278ms
memory: 405636kb
input:
4000 -+++---+-------+-++++-+++-++-+--++----++++++---+---++-++++-+++-++++-+---+--+++-----+-+--++-+--+-++++--+--++-+---+++++++++-+++++++-+++--+-+---++-+-++----+-++--++-++++++++++++++-+++-++-+++-++-++---+---+++-+-+++++++--+-+++-++-+-----+++-++--+++------+++--+++---+--+----++-+--+-+---+--+---+-+-+--++++...
output:
Yes 10001110111111101000010001001011001111000000111011100100001000100001011101100011111010110010110100001101100101110000000001000000010001101011100101001111010011001000000000000001000100100010010011101110001010000000110100010010111110001001100011111100011000111011011110010110101110110111010101100001...
result:
ok n=4000
Test #14:
score: 0
Accepted
time: 890ms
memory: 405716kb
input:
4000 +--+++++--++--+-+++-++-+-+-+-+--++------++++---+++-+-+--+------++-+--++-+-+++-----+-+++++-+------++++-++++-+--+------++--+++++-+-+--+-+++++++++++++++-+--+-+-+---+-+-+++++-++--+-+---++-++--+--+-+++-+-+++++-+--++-+----+++-++-++++-+---+--+-++-++-+-+-+---++-++-+-+----++-++++-----------+++--++++-++-...
output:
Yes 01100000110011010001001010101011001111110000111000101011011111100101100101000111110100000101111110000100001011011111100110000010101101000000000000000101101010111010111111011001010001101100100101110101111101001101000011101101111010001001011011010101000110110101000011011110000000000011100111101101...
result:
ok n=4000
Test #15:
score: 0
Accepted
time: 1535ms
memory: 405648kb
input:
4000 ---++-++-+-+----++-++++-----------+++--++++-++-++--+-+--+--+-+-++++--++-++--+++++--++--+-+----+-+---++-+++-+--+-++++++++-++---++++-+--+-+++---+-+--+--+-+--+--++++++-+---++++++-++++----+-+-+-++--+---+--+-+++--++++++-+++-+---+--+-----------++-+++--+++++++--++-+++++--+++-+-+++++++++--+---+++--+-+-...
output:
Yes 10011000110100001001111010000010001110011100110110011000110101010111011000000101100110010000001011000111100101101011011101100000011100001100001100010111001111100100010101101111100100001001100001001001010001001001110011011001001100010000001001001101111111001001110000110101011011110110001100010110...
result:
ok n=4000
Test #16:
score: -100
Time Limit Exceeded
input:
4000 ++-+-------+--++-++-++--++-+++++-++++--+-----++-+--+---++++--+-----++++++---+--+---+------+++-+-----+-+++--+++-+-+-+++-----++---+-+---+-+++++-+--+-++--++-+-----++-+-+---+++-+----++++---++--+-+-++-++-+--++---+++------++-+-++++--+--++-++-+++-++-+--++----++---+-+++-+-+++-++-+--++-++++--++-+-+-+-+-...