QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#497471 | #7669. Maze Reduction | Max_s_xaM | AC ✓ | 528ms | 112084kb | C++14 | 4.0kb | 2024-07-29 09:33:04 | 2024-07-29 09:33:04 |
Judging History
answer
#include <iostream>
#include <vector>
typedef long long ll;
typedef double lf;
// #define DEBUG 1
struct IO
{
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}
~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
#endif
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
#define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')
template <typename T>
void Read(T &x)
{
#if DEBUG
std::cin >> x;
#else
bool sign = 0; char ch = gc(); x = 0;
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
if (sign) x = -x;
#endif
}
void Read(char *s)
{
#if DEBUG
std::cin >> s;
#else
char ch = gc();
for (; blank(ch); ch = gc());
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
#endif
}
void Read(char &c) {for (c = gc(); blank(c); c = gc());}
void Push(const char &c)
{
#if DEBUG
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}
template <typename T>
void Write(T x)
{
if (x < 0) x = -x, Push('-');
static T sta[35];
int top = 0;
do sta[top++] = x % 10, x /= 10; while (x);
while (top) Push(sta[--top] ^ 48);
}
template <typename T>
void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)
using namespace std;
const int MAXN = 110, MAXM = 1e6 + 10;
int n;
vector <int> e[MAXN];
int id[MAXN][MAXN];
bool avl[MAXN]; int ans[MAXN];
int st[MAXM][3], top;
bool f[MAXN][MAXN][MAXN], vis[MAXN][MAXN][MAXN], inq[MAXN][MAXN][MAXN];
inline bool Solve(int u, int v, int d)
{
if (vis[u][v][d]) return f[u][v][d];
vis[u][v][d] = 1;
top++, st[top][0] = u, st[top][1] = v, st[top][2] = d;
inq[u][v][d] = 1;
if (e[u].size() != e[v].size()) return f[u][v][d] = 0;
bool flag = 1;
for (int i = 0, j = d; i < e[u].size(); i++, (++j == e[u].size()) && (j = 0))
{
int t = max(e[e[v][j]].size(), e[e[u][i]].size());
int dd = (id[e[v][j]][v] - id[e[u][i]][u] + t) % t;
if (inq[e[u][i]][e[v][j]][dd]) continue;
flag &= Solve(e[u][i], e[v][j], dd);
}
return f[u][v][d] = flag;
}
int main()
{
#if DEBUG
#else
ios::sync_with_stdio(0), cin.tie(0);
#endif
Read(n);
for (int i = 1; i <= n; i++)
{
int m; Read(m);
for (int j = 1, x; j <= m; j++) Read(x), e[i].push_back(x), id[i][x] = e[i].size() - 1;
}
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
{
int t = max(e[i].size(), e[j].size());
for (int k = 0; k < t; k++)
{
if (vis[i][j][k]) continue;
bool cur = Solve(i, j, k);
while (top) f[st[top][0]][st[top][1]][st[top][2]] = cur, inq[st[top][0]][st[top][1]][st[top][2]] = 0, top--;
}
}
bool flag = 0;
for (int i = 1; i <= n; i++)
if (!avl[i])
{
int cnt = 0;
ans[++cnt] = i;
for (int j = i + 1; j <= n; j++)
{
int t = max(e[i].size(), e[j].size());
if (t == 0) {ans[++cnt] = j; continue;}
for (int k = 0; k < t; k++)
if (f[i][j][k]) {ans[++cnt] = j; break;}
}
if (cnt > 1)
{
for (int i = 1; i <= cnt; i++) cout << ans[i] << ' ', avl[ans[i]] = 1; cout << '\n';
flag = 1;
}
}
if (!flag) cout << "none\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5928kb
input:
13 2 2 4 3 1 3 5 2 2 4 3 1 3 6 2 2 6 2 4 5 2 8 9 2 7 9 2 7 8 2 11 13 2 10 12 2 11 13 2 10 12
output:
2 4 5 6 7 8 9 10 11 12 13
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 7776kb
input:
6 3 3 4 5 0 1 1 1 1 2 1 6 1 5
output:
none
result:
ok single line: 'none'
Test #3:
score: 0
Accepted
time: 1ms
memory: 5872kb
input:
10 2 2 3 2 1 3 3 1 2 4 2 3 5 2 4 6 2 5 7 2 6 8 2 7 9 2 8 10 1 9
output:
none
result:
ok single line: 'none'
Test #4:
score: 0
Accepted
time: 0ms
memory: 7940kb
input:
10 2 2 3 2 1 3 3 1 2 4 2 3 5 2 4 6 2 5 7 2 6 8 3 7 9 10 2 8 10 2 8 9
output:
1 9 2 10 3 8 4 7 5 6
result:
ok 5 lines
Test #5:
score: 0
Accepted
time: 1ms
memory: 5768kb
input:
1 0
output:
none
result:
ok single line: 'none'
Test #6:
score: 0
Accepted
time: 0ms
memory: 5760kb
input:
2 0 0
output:
1 2
result:
ok single line: '1 2 '
Test #7:
score: 0
Accepted
time: 1ms
memory: 5696kb
input:
2 1 2 1 1
output:
1 2
result:
ok single line: '1 2 '
Test #8:
score: 0
Accepted
time: 1ms
memory: 5600kb
input:
3 0 0 0
output:
1 2 3
result:
ok single line: '1 2 3 '
Test #9:
score: 0
Accepted
time: 1ms
memory: 5804kb
input:
3 1 3 0 1 1
output:
1 3
result:
ok single line: '1 3 '
Test #10:
score: 0
Accepted
time: 1ms
memory: 5800kb
input:
3 2 2 3 2 3 1 2 2 1
output:
1 2 3
result:
ok single line: '1 2 3 '
Test #11:
score: 0
Accepted
time: 0ms
memory: 7700kb
input:
4 1 2 2 1 3 2 2 4 1 3
output:
1 4 2 3
result:
ok 2 lines
Test #12:
score: 0
Accepted
time: 1ms
memory: 5728kb
input:
4 1 3 1 3 3 4 1 2 1 3
output:
1 2 4
result:
ok single line: '1 2 4 '
Test #13:
score: 0
Accepted
time: 0ms
memory: 5696kb
input:
4 2 4 3 2 3 4 2 1 2 2 2 1
output:
1 2 3 4
result:
ok single line: '1 2 3 4 '
Test #14:
score: 0
Accepted
time: 0ms
memory: 5672kb
input:
4 2 4 3 2 3 4 3 1 2 4 3 2 3 1
output:
3 4
result:
ok single line: '3 4 '
Test #15:
score: 0
Accepted
time: 1ms
memory: 7756kb
input:
4 2 4 3 2 3 4 3 1 2 4 3 2 1 3
output:
1 2 3 4
result:
ok 2 lines
Test #16:
score: 0
Accepted
time: 1ms
memory: 5960kb
input:
15 2 2 3 3 1 4 5 3 1 6 7 3 2 8 9 3 2 10 11 3 3 12 13 3 3 14 15 1 4 1 4 1 5 1 5 1 6 1 6 1 7 1 7
output:
2 3 4 6 5 7 8 12 9 13 10 14 11 15
result:
ok 7 lines
Test #17:
score: 0
Accepted
time: 1ms
memory: 6400kb
input:
31 2 2 3 3 1 4 5 3 1 6 7 3 2 8 9 3 2 10 11 3 3 12 13 3 3 14 15 3 4 16 17 3 4 18 19 3 5 20 21 3 5 22 23 3 6 24 25 3 6 26 27 3 7 28 29 3 7 30 31 1 8 1 8 1 9 1 9 1 10 1 10 1 11 1 11 1 12 1 12 1 13 1 13 1 14 1 14 1 15 1 15
output:
2 3 4 6 5 7 8 12 9 13 10 14 11 15 16 24 17 25 18 26 19 27 20 28 21 29 22 30 23 31
result:
ok 15 lines
Test #18:
score: 0
Accepted
time: 0ms
memory: 7712kb
input:
63 2 2 3 3 1 4 5 3 1 6 7 3 2 8 9 3 2 10 11 3 3 12 13 3 3 14 15 3 4 16 17 3 4 18 19 3 5 20 21 3 5 22 23 3 6 24 25 3 6 26 27 3 7 28 29 3 7 30 31 3 8 32 33 3 8 34 35 3 9 36 37 3 9 38 39 3 10 40 41 3 10 42 43 3 11 44 45 3 11 46 47 3 12 48 49 3 12 50 51 3 13 52 53 3 13 54 55 3 14 56 57 3 14 58 59 3 15 60...
output:
2 3 4 6 5 7 8 12 9 13 10 14 11 15 16 24 17 25 18 26 19 27 20 28 21 29 22 30 23 31 32 48 33 49 34 50 35 51 36 52 37 53 38 54 39 55 40 56 41 57 42 58 43 59 44 60 45 61 46 62 47 63
result:
ok 31 lines
Test #19:
score: 0
Accepted
time: 0ms
memory: 9036kb
input:
91 8 3 19 31 43 87 30 78 13 4 80 18 24 81 8 87 78 13 1 43 19 30 31 12 54 8 59 67 79 22 91 41 57 83 17 25 11 16 64 58 61 84 12 7 32 45 85 15 7 76 63 68 82 71 69 33 11 32 16 84 85 5 45 15 12 58 64 61 12 41 79 54 4 91 67 83 22 59 57 17 25 10 49 34 86 77 53 60 89 23 72 50 9 29 75 62 37 44 51 35 47 21 2 ...
output:
1 3 13 19 30 31 43 78 87 2 18 24 80 81 4 8 17 22 25 41 54 57 59 67 79 83 91 5 7 12 15 16 32 45 58 61 64 84 85 6 33 63 68 69 71 76 82 9 23 34 49 50 53 60 72 77 86 89 10 21 29 35 37 44 47 51 62 75 11 27 65 14 39 48 55 56 70 20 26 28 38 46 66 74 36 90 40 42 52 73
result:
ok 12 lines
Test #20:
score: 0
Accepted
time: 528ms
memory: 112084kb
input:
100 99 31 20 72 66 27 54 67 85 78 11 59 44 77 38 89 47 13 15 33 4 23 86 22 28 32 80 43 39 51 75 25 88 37 69 3 12 50 84 30 76 56 57 29 46 19 63 87 55 18 96 16 53 26 10 62 34 8 36 99 93 91 73 81 83 97 7 52 60 94 68 58 6 79 65 14 61 40 71 42 70 24 90 2 64 98 92 49 82 74 21 41 48 45 95 9 35 17 5 100 99 ...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ...91 92 93 94 95 96 97 98 99 100 '
Test #21:
score: 0
Accepted
time: 25ms
memory: 21004kb
input:
50 49 18 36 12 40 6 29 31 24 27 11 7 39 28 33 44 42 23 16 3 41 46 38 13 30 45 37 14 25 15 34 47 8 49 26 48 20 43 35 32 10 19 22 21 4 5 17 9 2 50 49 8 6 38 29 32 37 4 7 11 18 22 41 45 48 17 21 14 43 40 24 9 34 35 47 44 33 1 28 5 46 20 27 12 39 50 36 15 10 49 31 25 13 3 30 23 19 16 26 42 49 26 25 6 24...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ... 41 42 43 44 45 46 47 48 49 50 '
Test #22:
score: 0
Accepted
time: 1ms
memory: 7760kb
input:
8 3 2 3 5 3 6 4 1 3 1 4 7 3 2 8 3 3 7 6 1 3 8 2 5 3 3 8 5 3 7 4 6
output:
1 2 3 4 5 6 7 8
result:
ok single line: '1 2 3 4 5 6 7 8 '
Test #23:
score: 0
Accepted
time: 1ms
memory: 5856kb
input:
8 4 2 4 3 5 3 6 4 1 3 1 4 7 4 1 2 8 3 3 7 6 1 3 8 2 5 3 3 8 5 3 7 4 6
output:
1 4 2 3 5 8 6 7
result:
ok 4 lines
Test #24:
score: 0
Accepted
time: 1ms
memory: 5840kb
input:
8 4 2 8 3 5 3 6 4 1 3 1 4 7 3 2 8 3 3 7 6 1 3 8 2 5 3 3 8 5 4 7 4 6 1
output:
1 8 2 6 3 7 4 5
result:
ok 4 lines
Test #25:
score: 0
Accepted
time: 1ms
memory: 5912kb
input:
8 4 2 3 5 4 3 6 4 1 3 1 4 7 4 2 8 3 1 3 7 6 1 3 8 2 5 3 3 8 5 3 7 4 6
output:
none
result:
ok single line: 'none'
Test #26:
score: 0
Accepted
time: 3ms
memory: 9180kb
input:
100 2 50 13 2 8 45 2 93 91 2 61 23 2 22 48 2 30 24 2 64 51 2 98 2 2 35 58 2 41 25 2 54 34 2 63 19 2 1 21 2 42 79 2 26 90 2 24 96 2 27 66 2 40 47 2 12 39 2 99 60 2 13 99 2 69 5 2 4 77 2 6 16 2 10 85 2 71 15 2 84 17 2 51 87 2 86 40 2 46 6 2 53 41 2 38 88 2 66 68 2 11 52 2 97 9 2 48 82 2 83 98 2 52 32 ...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ...91 92 93 94 95 96 97 98 99 100 '
Test #27:
score: 0
Accepted
time: 0ms
memory: 9304kb
input:
100 3 50 2 13 3 8 45 1 2 93 91 2 61 23 2 22 48 2 30 24 2 64 51 2 98 2 2 35 58 2 41 25 2 54 34 2 63 19 2 1 21 2 42 79 2 26 90 2 24 96 2 27 66 2 40 47 2 12 39 2 99 60 2 13 99 2 69 5 2 4 77 2 6 16 2 10 85 2 71 15 2 84 17 2 51 87 2 86 40 2 46 6 2 53 41 2 38 88 2 66 68 2 11 52 2 97 9 2 48 82 2 83 98 2 52...
output:
1 2 3 40 4 7 5 90 6 96 8 13 9 17 10 52 11 85 12 94 14 79 15 48 16 24 18 93 19 59 20 83 21 98 22 65 23 64 25 34 26 36 27 58 28 80 29 91 30 75 31 32 33 97 35 66 37 99 38 41 39 55 42 44 43 46 45 50 47 57 49 70 51 61 53 88 54 62 56 89 60 77 63 78 67 74 68 76 6...
result:
ok 50 lines
Test #28:
score: 0
Accepted
time: 1ms
memory: 6104kb
input:
25 3 2 6 7 3 3 1 8 3 4 2 9 3 5 3 10 3 6 4 11 3 1 5 12 1 1 2 2 13 1 3 2 4 14 1 5 2 6 15 1 8 1 10 1 12 3 19 17 20 3 21 16 18 3 17 19 22 3 16 23 18 2 16 24 1 17 2 18 25 1 19 1 20 1 22
output:
1 3 5 17 19 2 4 6 16 18 7 9 11 21 23 8 10 12 20 22 13 14 15 24 25
result:
ok 5 lines
Test #29:
score: 0
Accepted
time: 1ms
memory: 5884kb
input:
10 6 2 3 4 5 6 7 1 1 2 1 8 1 1 2 9 1 1 1 2 1 10 1 3 1 5 1 7
output:
2 4 6 3 5 7 8 9 10
result:
ok 3 lines
Test #30:
score: 0
Accepted
time: 1ms
memory: 7804kb
input:
10 6 2 4 3 5 6 7 1 1 2 1 8 1 1 2 9 1 1 1 2 1 10 1 3 1 5 1 7
output:
none
result:
ok single line: 'none'
Test #31:
score: 0
Accepted
time: 2ms
memory: 9292kb
input:
100 3 15 78 6 3 52 8 51 4 71 57 40 48 1 54 2 50 7 1 1 2 75 5 2 38 2 1 81 2 82 20 2 94 27 1 44 2 92 52 3 91 16 81 2 77 1 2 81 14 1 69 3 56 69 53 1 81 3 76 10 74 1 58 3 63 46 55 2 100 79 1 70 1 97 2 96 52 2 81 11 5 49 95 71 39 62 2 96 43 1 82 3 70 86 33 1 84 2 47 31 2 45 35 2 60 34 3 61 83 58 1 66 1 8...
output:
none
result:
ok single line: 'none'
Test #32:
score: 0
Accepted
time: 8ms
memory: 14304kb
input:
100 18 35 83 94 49 12 21 53 15 88 71 22 41 31 99 57 32 70 66 20 69 63 87 58 70 98 29 65 32 41 39 99 53 28 36 8 51 47 25 79 19 68 24 86 14 51 71 53 5 89 11 57 42 32 43 36 69 30 27 79 17 32 23 10 94 16 85 43 6 65 75 48 60 64 80 39 15 63 14 41 42 78 36 65 29 3 12 66 84 54 75 23 82 20 32 40 74 17 8 57 9...
output:
none
result:
ok single line: 'none'
Test #33:
score: 0
Accepted
time: 0ms
memory: 7080kb
input:
50 3 25 28 4 3 18 9 14 2 44 36 2 43 1 2 21 12 3 46 7 35 2 10 6 1 16 3 31 40 2 3 44 7 27 1 26 2 42 5 2 28 17 1 2 2 34 20 2 45 8 1 13 2 47 2 1 21 2 48 15 2 19 5 2 31 24 1 40 1 22 3 47 1 38 2 44 11 2 28 10 5 49 1 13 27 29 1 28 1 40 2 22 9 1 39 1 37 2 45 15 1 6 4 41 50 3 42 2 43 33 1 25 2 48 32 4 23 30 ...
output:
none
result:
ok single line: 'none'
Test #34:
score: 0
Accepted
time: 0ms
memory: 7740kb
input:
50 21 24 30 31 27 34 50 38 4 33 3 15 22 19 35 11 49 26 46 10 43 29 21 24 50 20 42 15 19 27 25 47 46 11 21 44 30 12 7 4 9 17 31 23 18 4 9 1 46 24 6 26 31 36 34 23 20 44 15 25 27 10 38 20 23 32 18 15 2 1 34 20 39 36 19 3 14 25 13 16 28 37 12 31 15 30 32 25 50 17 14 15 42 38 48 20 47 27 6 33 21 35 47 4...
output:
none
result:
ok single line: 'none'