QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#134954 | #6634. Central Subset | Orange_JuiCE# | WA | 10ms | 13884kb | C++17 | 2.7kb | 2023-08-05 10:18:23 | 2023-08-05 10:18:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#define rep(a, b, c) for(int (a)=(b);(a)<=(c);(a)++)
#define per(a, b, c) for(int (a)=(b);(a)>=(c);(a)--)
#define mset(var, val) memset(var,val,sizeof(var))
#define ll long long
#define int ll
#define fi first
#define se second
#define no "NO\n"
#define yes "YES\n"
#define pb push_back
#define endl "\n"
#define pii pair<int,int>
#define pll pair<ll,ll>
#define dbg(x...) do{cout<<#x<<" -> ";err(x);}while (0)
void err() { cout << '\n'; }
template<class T, class... Ts>
void err(T arg, Ts... args) {
cout << arg << ' ';
err(args...);
}
const int N = 2e5 + 5;
const int M = 1e6 + 5;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int P = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1.0);
int n, m, sqn, s, t, mid, cnt, fa[N], dep[N], mx_dp[N];
int tot=0, lnk[N], son[M<<1], nxt[M<<1];
bool f[N], vis[N];
void add(int x, int y) {
son[++tot] = y, nxt[tot] = lnk[x], lnk[x] = tot;
}
void dfs1(int u) {
for(int i = lnk[u]; i != -1; i = nxt[i]) {
int v = son[i];
if(vis[v]) continue;
dep[v] = dep[u]+1, vis[v] = 1, fa[v] = u;
dfs1(v);
}
}
void dfs2(int u) {
mx_dp[u] = 1;
for(int i = lnk[u]; i != -1; i = nxt[i]) {
int v = son[i];
if(vis[v]) continue;
vis[v] = 1;
dfs2(v);
mx_dp[u] = max(mx_dp[u], mx_dp[v]+1);
}
if(mx_dp[u] > sqn && u != mid) {
f[u]=1;
cnt++;
}
}
void solve() {
cin >> n >> m;
sqn = sqrt(n-1)+1, tot=0;
for(int i = 1; i <= n; i++)
f[i] = 0, lnk[i] = -1,vis[i]=0;
for(int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
add(x, y);
add(y, x);
}
vis[1]=1, dep[1]=1, fa[1]=1;
dfs1(1);
s=1;
for(int i = 1; i <= n; i++) {
vis[i]=0;
if(dep[i] > dep[s]) s = i;
// printf("%d dep%d fa%d\n", i, dep[i], fa[i]);
}
vis[s]=1, dep[s]=1, fa[s]=1;
dfs1(s);
t=s;
for(int i = 1; i <= n; i++) {
vis[mid]=0;
if(dep[i] > dep[t]) t = i;
// printf("%d dep%d fa%d\n", i, dep[i], fa[i]);
}
mid = t;
while(dep[mid] != dep[t]/2) mid = fa[mid];
// printf("mid%d\n", mid);
cnt=1, vis[mid] = 1, f[mid] = 1;
dfs2(mid);
if(cnt <= sqn) {
printf("%d\n", cnt);
for(int i = 1; i <= n; i++)
if(f[i]) printf("%d ", i);
printf("\n");
}
else printf("-1\n");
}
signed main() {
IOS;
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11820kb
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 3 1 4
result:
ok correct (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 10ms
memory: 13884kb
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 9 1 3 1 4 1 2 1 2 1 6 1 2 1 5 1 10 1 3 1 11 1 4 1 4 1 10 1 3 1 9 1 4 1 2 1 4 1 3 1 3 1 4 1 5 1 8 1 3 1 9 1 3 1 6 1 3 1 3 1 12 1 5 1 5 1 7 1 3 1 4 1 4 1 5 1 6 1 3 1 7 1 3 1 5 1 3 1 3 1 6 1 6 1 5 1 7 1 3 1 10 1 4 1 4 1 6 1 3 1 9 1 4 1 4 1 3 ...
result:
wrong answer Condition failed: "getMaxBfsDist(n, subset) <= csqrtn" (test case 1)