QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#569035 | #9310. Permutation Counting 4 | CangShuV | WA | 81ms | 3688kb | C++23 | 1.1kb | 2024-09-16 20:04:20 | 2024-09-16 20:04:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
vector<int> g[N];
void add(int f, int t) {
g[f].push_back(t);
g[t].push_back(f);
}
int st[N];
int res = 0;
void dfs(int u, int pa) {
st[u] = 1;
if (res)
return;
for (auto it : g[u]) {
if (it == pa)
continue;
if (st[it]) {
res = 1;
return;
}
dfs(it, u);
if (res)
return;
}
}
void clr(int n) {
res = 0;
memset(st, 0, sizeof(int) * (n + 1));
for (int i = 0; i <= n; ++i)
g[i].clear();
}
void solve() {
int n;
cin >> n;
clr(n);
while (n--) {
int a, b;
cin >> a >> b;
add(a - 1, b);
}
dfs(0, -1);
if (res) {
cout << "0\n";
return;
}
for (int i = 0; i <= n; ++i)
if (!st[i]) {
cout << "0\n";
return;
}
cout << "1\n";
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t; // ft.
while (t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3688kb
input:
4 5 1 2 1 5 1 2 1 2 2 2 5 1 1 2 4 2 3 5 5 3 4 5 3 5 1 2 3 4 3 5 3 3 5 1 5 1 4 4 5 5 5 1 2
output:
0 1 0 0
result:
ok 4 tokens
Test #2:
score: -100
Wrong Answer
time: 81ms
memory: 3632kb
input:
66725 14 7 7 4 6 7 8 8 13 2 13 6 13 6 10 14 14 1 10 9 11 7 9 3 8 4 12 5 12 12 2 6 3 6 7 11 2 5 1 1 6 12 8 12 2 3 7 9 7 8 1 10 1 4 10 4 8 4 4 6 10 9 10 2 3 2 7 1 3 3 4 2 2 3 10 20 3 12 10 14 19 20 19 20 1 9 7 9 13 16 17 17 16 18 2 11 5 19 6 17 11 17 3 6 3 11 7 20 8 17 3 18 10 15 9 20 16 5 10 2 10 2 1...
output:
1 1 0 0 1 0 1 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 1 1 1 0 1 0 0 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 1 0 1 0 1 1 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 0 1 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 0 1 1 ...
result:
wrong answer 12th words differ - expected: '0', found: '1'