QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#84557 | #5523. Graph Problem With Small $n$ | lnyx | TL | 1856ms | 38056kb | C++14 | 1.7kb | 2023-03-06 15:52:40 | 2023-03-06 15:52:43 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <cstdio>
#include <iostream>
namespace IO {
template<typename T> inline void rd(T& x) {
x = 0; bool f = 0; char s = getchar();
while (s < '0' || s > '9') f |= s == '-', s = getchar();
while ('0' <= s && s <= '9') x = x * 10 + (s - '0'), s = getchar();
x = f ? -x : x;
}
template<typename T, typename ...Args> inline void rd(T& x, Args& ...args) { rd(x), rd(args...); }
template<typename T> inline void wt(T x, char s) {
int stk[114], top = 0;
if (x < 0) putchar('-'), x = -x;
do stk[ ++ top] = x % 10, x /= 10; while (x);
while (top) putchar(stk[top -- ] + '0');
putchar(s);
}
}
using namespace IO;
using namespace std;
const int N = 27;
char s[N];
int g[N];
int n, all;
int f[(1 << 24) + 7];
int ans[N];
inline int dp(int s) {
if (f[s] != -1) return f[s];
f[s] = 0;
for (int i = 1; i <= n; ++ i) {
if (!((s >> (i - 1)) & 1)) continue;
// if (s == 7) cerr << i << " " << dp(s ^ (1 << (i - 1))) << " " << g[i] << endl;
f[s] |= (!!(dp(s ^ (1 << (i - 1))) & g[i])) << (i - 1);
}
return f[s];
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
rd(n), all = (1 << n) - 1;
for (int i = 1; i <= n; ++ i) {
scanf("%s", s + 1);
for (int j = 1; j <= n; ++ j) {
g[i] += (s[j] - '0') << (j - 1);
}
}
for (int i = 0; i <= all; ++ i) f[i] = -1;
f[1] = 1;
dp(all);
for (int i = 1; i <= n; ++ i) {
for (int s = 0; s <= all; ++ s) {
if ((f[s] >> (i - 1)) & 1) ans[i] |= f[all ^ s ^ 1];
}
}
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) {
putchar(((ans[i] >> (j - 1)) & 1) + '0');
}
putchar('\n');
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3536kb
input:
4 0110 1010 1101 0010
output:
0001 0001 0000 1100
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 3396kb
input:
6 010001 101000 010100 001010 000101 100010
output:
010001 101000 010100 001010 000101 100010
result:
ok 6 lines
Test #3:
score: 0
Accepted
time: 2ms
memory: 3368kb
input:
4 0111 1011 1101 1110
output:
0111 1011 1101 1110
result:
ok 4 lines
Test #4:
score: 0
Accepted
time: 1631ms
memory: 36536kb
input:
23 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 000000000...
output:
00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 000000000000...
result:
ok 23 lines
Test #5:
score: 0
Accepted
time: 1615ms
memory: 37780kb
input:
23 00010100000000000101000 00000000010000000001000 00000000000001000000001 10000000000000000010000 00000000000000000000000 10000000000000000000000 00000001000000000000000 00000010000000000010000 00000000000001000000000 01000000000000000000000 00000000000000000000000 00000000000000000000000 000000000...
output:
00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 000000000000...
result:
ok 23 lines
Test #6:
score: 0
Accepted
time: 1601ms
memory: 36120kb
input:
23 00001000000000000000000 00001000010001000000000 00000000000101000010000 00001000000100000000000 11010000010011000100000 00000000000100000000000 00000000000000000000001 00000000000000000101000 00000000000000000000000 01001000000000101010010 00000000000000000000101 00110100000010001000000 000010000...
output:
00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 000000000000...
result:
ok 23 lines
Test #7:
score: 0
Accepted
time: 1638ms
memory: 36240kb
input:
23 01000000000001101001100 10000001101000000000000 00000100000100010000100 00000000000000001011000 00000100001000000000000 00101000000000001000001 00000000000000000000000 01000000000000000000000 01000000000100000010000 00000000000001000000011 01001000000000010000000 00100000100001000100001 000000000...
output:
00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 000000000000...
result:
ok 23 lines
Test #8:
score: 0
Accepted
time: 1588ms
memory: 37924kb
input:
23 00000000010001001001010 00100010001101110000001 01000001000100110000000 00000011010001101100100 00000000010000010001000 00000000000000001001000 01010001000000000000001 00110010000000000000010 00000000011000100100000 10011000101000100000000 01000000110010101010000 01100000000000000000000 000000000...
output:
01111111110111110110111 10011111110111110110111 10011111110111110110111 11101111110110110110111 11110111110111110110111 11111011110111111111111 11111101110111110110111 11111110110111110110111 11111111010111110110111 11111111100110100110111 00000000000010000010100 11111111110011110110111 111111111111...
result:
ok 23 lines
Test #9:
score: 0
Accepted
time: 1745ms
memory: 36296kb
input:
23 00001000001001000000000 00101100111110100000000 01001000100001011010000 00000000010000010010000 11100001100001000000010 01000010101010100011011 00000100000100100010000 00001000011000000010001 01101100000000011001001 01010001000010011000000 11000101000110001100000 01000010001000000000010 010001000...
output:
00000000000000000000100 00000000000000000000100 00000000000000000000100 00000000000000000000100 00000000000000000000100 00000000000000000000100 00000000000000000000100 00000000000000000000100 00000000000000000000100 00000000000000000000100 00000000000000000000100 00000000000000000000100 000000000000...
result:
ok 23 lines
Test #10:
score: 0
Accepted
time: 1592ms
memory: 37544kb
input:
23 00001011110010000000001 00000100000011000000100 00010011010100000000011 00100011011001010100100 10000101000110100000000 01001000001010001000100 10110000000110000010000 10111000001100010100010 10000000000010001000110 10110000001110100110001 00010101010100001000000 00101011011000100100011 110011101...
output:
00000000000000000001000 00000000000000000001000 00000000000000000001000 00000000000000000001000 00000000000000000001000 00000000000000000001000 00000000000000000001000 00000000000000000001000 00000000000000000001000 00000000000000000001000 00000000000000000001000 00000000000000000001000 000000000000...
result:
ok 23 lines
Test #11:
score: 0
Accepted
time: 1615ms
memory: 37920kb
input:
23 00100100001000000100001 00101110110000100100001 11000000000101001000100 00000000010000001111010 01000011010001011001010 11000000010100001001011 01001000001010101000100 00001000001010000000000 01000000000001100001011 01011100001101100000000 10000011010010100000010 00100100010000000001000 000000110...
output:
01111111111111111111111 10111111111111111111111 11011111111111111111111 11101111111111111111111 11110111111111111111111 11111011111111111111111 11111101111111111111111 11111110111111111111111 11111111011111111111111 11111111101111111111111 11111111110111111111111 11111111111011111111111 111111111111...
result:
ok 23 lines
Test #12:
score: 0
Accepted
time: 1595ms
memory: 38056kb
input:
23 00000001011001011100100 00000001010000000010100 00000001010010100010000 00001000100111100000000 00010100011000010111001 00001000100001000010010 00000001111001100011000 11100010111100110001001 00010111010000101100110 11101011100000100100100 10001011000010100000010 00010001000001011101110 001100000...
output:
01111111111111111111111 10111111111111111111111 11011111111111111111111 11101111111111111111111 11110111111111111111111 11111011111111111111111 11111101111111111111111 11111110111111111111111 11111111011111111111111 11111111101111111111111 11111111110111111111111 11111111111011111111111 111111111111...
result:
ok 23 lines
Test #13:
score: 0
Accepted
time: 1631ms
memory: 36164kb
input:
23 00100100001101000100000 00010111011000100000010 10000010010001111000010 01001011101001000100000 00010000010110000100111 11000000101000011101001 01110001100000010101100 01010010001001010100000 00010110001100010010001 01101000000011000111000 11010101100010010001101 10001000100010001110100 000010000...
output:
01111111111111111111111 10111111111111111111111 11011111111111111111111 11101111111111111111111 11110111111111111111111 11111011111111111111111 11111101111111111111111 11111110111111111111111 11111111011111111111111 11111111101111111111111 11111111110111111111111 11111111111011111111111 111111111111...
result:
ok 23 lines
Test #14:
score: 0
Accepted
time: 1679ms
memory: 36024kb
input:
23 01001101001011010101100 10001010111100100001110 00000000010101000111100 00000000001010010100010 11000000100110000111000 10000010001000010101000 01000100100010001100101 10000000010001000110110 01001010000001111100000 01100001000001001101001 11010100000011001010111 01101000000000100100110 100110100...
output:
01111111111111111111111 10111111111111111111111 11011111111111111111111 11101111111111111111111 11110111111111111111111 11111011111111111111111 11111101111111111111111 11111110111111111111111 11111111011111111111111 11111111101111111111111 11111111110111111111111 11111111111011111111111 111111111111...
result:
ok 23 lines
Test #15:
score: 0
Accepted
time: 1633ms
memory: 36048kb
input:
23 01100101000101001000001 10111000100000010110010 11011010011101000010010 01100010001111011011111 01100010011110001111100 10000000011000001011010 00111001001000101100111 10000010110110011000000 01000001001110010100100 00101101000100111100001 00111110100110011011010 10111001111010001010000 000110011...
output:
01111111111111111111111 10111111111111111111111 11011111111111111111111 11101111111111111111111 11110111111111111111111 11111011111111111111111 11111101111111111111111 11111110111111111111111 11111111011111111111111 11111111101111111111111 11111111110111111111111 11111111111011111111111 111111111111...
result:
ok 23 lines
Test #16:
score: 0
Accepted
time: 1856ms
memory: 36140kb
input:
23 01111001001110001000101 10000000000100111111110 10010101000110100100101 10101000001010010101001 10010010011110101101111 00100000101100011000000 00001000011000010001101 10100000010000000000100 00000100010110001111100 00001011100101010110111 10011110000000010101101 11101100110010010100000 101110001...
output:
01111111111111111111111 10111111111111111111111 11011111111111111111111 11101111111111111111111 11110111111111111111111 11111011111111111111111 11111101111111111111111 11111110111111111111111 11111111011111111111111 11111111101111111111111 11111111110111111111111 11111111111011111111111 111111111111...
result:
ok 23 lines
Test #17:
score: 0
Accepted
time: 1820ms
memory: 36160kb
input:
23 01010000000100001110001 10000110010001110010100 00011000101111001010110 10101111011100101100111 00110011111111111011000 01010011100001111011011 01011100001111000011101 00011100001110111010010 00101100011101001000011 01011000100000000000010 00111011100001001000111 10111011100000110100001 001010110...
output:
01111111111111111111111 10111111111111111111111 11011111111111111111111 11101111111111111111111 11110111111111111111111 11111011111111111111111 11111101111111111111111 11111110111111111111111 11111111011111111111111 11111111101111111111111 11111111110111111111111 11111111111011111111111 111111111111...
result:
ok 23 lines
Test #18:
score: 0
Accepted
time: 1642ms
memory: 36304kb
input:
23 00100101011111000101011 00100001000110000111101 11010000011110010110011 00101101110110000101110 00010101111001110101110 10011001111101010011101 00000000110011000000100 11011100110111001110110 00011111000000100110010 10111111000111101010010 10101100000111111010100 11110101011010101010010 111100110...
output:
01111111111111111111111 10111111111111111111111 11011111111111111111111 11101111111111111111111 11110111111111111111111 11111011111111111111111 11111101111111111111111 11111110111111111111111 11111111011111111111111 11111111101111111111111 11111111110111111111111 11111111111011111111111 111111111111...
result:
ok 23 lines
Test #19:
score: 0
Accepted
time: 1694ms
memory: 36956kb
input:
23 00100001100011011101011 00111011101101101011001 11001101100100001000111 01001010110101101000010 01110011001111000101111 00100011100000111101010 01011100000110101001100 11101100010110110011000 11110100010010000011010 00010001101011011011011 01001000010001001011111 01111011000010101011101 100010111...
output:
01111111111111111111111 10111111111111111111111 11011111111111111111111 11101111111111111111111 11110111111111111111111 11111011111111111111111 11111101111111111111111 11111110111111111111111 11111111011111111111111 11111111101111111111111 11111111110111111111111 11111111111011111111111 111111111111...
result:
ok 23 lines
Test #20:
score: -100
Time Limit Exceeded
input:
24 000000000000000000000000 000000000000000000000000 000000000000000000000000 000000000000000000000000 000000000000000000000000 000000000000000000000000 000000000000000000000000 000000000000000000000000 000000000000000000000000 000000000000000000000000 000000000000000000000000 0000000000000000000000...