QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#84557#5523. Graph Problem With Small $n$lnyxTL 1856ms38056kbC++141.7kb2023-03-06 15:52:402023-03-06 15:52:43

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-06 15:52:43]
  • 评测
  • 测评结果:TL
  • 用时:1856ms
  • 内存:38056kb
  • [2023-03-06 15:52:40]
  • 提交

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

output:


result: