QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#135256 | #6634. Central Subset | Orange_JuiCE# | WA | 13ms | 9832kb | C++17 | 2.5kb | 2023-08-05 13:15:43 | 2023-08-05 13:15:45 |
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, s, t, mid, sqn, cnt, in[N], dep[N];
int tot=0, lnk[N], son[M<<1], nxt[M<<1];
bool qaq[N], f[N];
queue<int>q;
void add(int x, int y) {
son[++tot] = y, nxt[tot] = lnk[x], lnk[x] = tot;
}
bool check(int x) {
if(x <= sqn) return 0;
int xx = x / (2*sqn);
xx = xx*2*sqn;
if(x-xx > sqn) return 1;
return 0;
}
void bfs2(int x) {
while(!q.empty()) q.pop();
dep[x] = 0, f[x] = 1, cnt = 1;
q.push(x);
while(!q.empty()) {
int u = q.front(), out=0, flg=0; q.pop();
for(int i = lnk[u]; i != -1; i = nxt[i]) {
int v = son[i];
if(dep[v] || v == x) continue;
dep[v] = dep[u]+1, out++;
if(dep[v]%sqn == 0 && flg==0) cnt++, f[v] = 1, flg=1;
q.push(v);
}
// if(qaq[dep[u]] || (!out && check(dep[u]) && u != x)) cnt++, f[u] = 1;
}
}
void solve() {
cin >> n >> m;
sqn = sqrt(n), tot=0;
for(int i = 1; i <= n; i++) {
lnk[i] = -1, dep[i] = 0, f[i] = 0;
if(i % (2*sqn) == 0) qaq[i] = 1;
else qaq[i] = 0;
}
for(int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
in[x]++, in[y]++;
add(x, y); add(y, x);
}
s=1;
for(int i = 1; i <= n; i++)
if(in[i] > in[s]) s = i;
cnt=0;
bfs2(s);
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 9832kb
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:
2 2 4 2 1 6
result:
ok correct (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 13ms
memory: 9828kb
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 2 2 5 -1 -1 3 2 5 8 -1 3 2 5 14 3 2 7 16 1 2 -1 -1 2 2 9 3 2 9 10 1 2 -1 -1 -1 2 2 9 1 2 2 2 4 -1 3 2 5 8 3 2 11 12 1 2 -1 -1 2 2 13 -1 1 2 -1 3 2 7 10 3 2 8 11 3 2 10 11 1 2 -1 2 2 5 2 2 5 4 2 8 16 18 1 2 -1 -1 2 2 10 2 2 4 1 2 3 2 5 8 2 2 8 2 2 10 -1 1 2 -1 4 2...
result:
wrong answer Integer -1 violates the range [1, 4] (test case 1)