QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#118859 | #6634. Central Subset | 8BQube# | WA | 11ms | 8104kb | C++20 | 1.1kb | 2023-07-04 14:12:01 | 2023-07-04 14:12:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()
#define pb push_back
vector<int> G[200005], ans;
int sqn, vis[200005];
int dfs(int u) {
vis[u] = 1;
int mx = -sqn - 1;
int cnt = 0;
for (int i : G[u])
if (!vis[i]) {
mx = max(dfs(i) + 1, mx);
++cnt;
}
if (!cnt) mx = 0;
else {
if (mx == sqn) ans.pb(u), mx = -sqn;
}
return mx;
}
void solve() {
int n, m;
cin >> n >> m;
ans.clear();
for (int i = 1; i <= n; ++i)
G[i].clear(), vis[i] = 0;
sqn = sqrt(n);
while (sqn * sqn < n) ++sqn;
while (m--) {
int a, b;
cin >> a >> b;
G[a].pb(b);
}
if (dfs(1) >= 0) ans.pb(1);
cout << SZ(ans) << "\n";
for (int i = 0; i < SZ(ans); ++i)
cout << ans[i] << " \n"[i + 1 == SZ(ans)];
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 8088kb
input:
2 4 3 1 2 2 3 3 4 6 7 1 2 2 3 3 1 1 4 4 5 5 6 6 4
output:
1 2 1 1
result:
ok correct (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 11ms
memory: 8104kb
input:
10000 15 14 13 12 5 4 9 8 11 12 15 14 10 9 14 13 2 3 2 1 6 5 10 11 3 4 7 6 8 7 6 5 2 1 2 4 4 6 2 3 3 5 10 9 8 3 9 4 5 6 5 10 3 2 5 4 2 7 1 2 4 3 2 1 2 1 2 1 2 1 9 8 9 8 5 4 1 2 6 5 3 4 3 2 7 8 7 6 2 1 1 2 14 13 3 10 5 6 2 9 11 4 2 3 2 1 8 7 13 6 5 4 5 12 6 7 4 3 7 14 16 15 2 3 2 1 6 10 6 9 6 4 9 11 ...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
wrong answer Condition failed: "getMaxBfsDist(n, subset) <= csqrtn" (test case 1)