QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#135256#6634. Central SubsetOrange_JuiCE#WA 13ms9832kbC++172.5kb2023-08-05 13:15:432023-08-05 13:15:45

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-05 13:15:45]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:9832kb
  • [2023-08-05 13:15:43]
  • 提交

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)