QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#134954#6634. Central SubsetOrange_JuiCE#WA 10ms13884kbC++172.7kb2023-08-05 10:18:232023-08-05 10:18:25

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 10:18:25]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:13884kb
  • [2023-08-05 10:18:23]
  • 提交

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)