QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#134908	#6634. Central Subset	kiwiHM^#	WA	13ms	9716kb	C++14	1.8kb	2023-08-05 09:56:00	2023-08-05 09:56:01

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 09:56:01]
评测

测评结果：WA
用时：13ms
内存：9716kb

查看

[2023-08-05 09:56:00]
提交

answer

#include <bits/stdc++.h>
using namespace std;

const int Maxn = 200500;

struct Enode{
    int u, v;
} E[1000500];

vector <int> son[Maxn], ans;
int dep[Maxn], maxd[Maxn], p[Maxn];
int n, m, LMT;

void cmax(int &x, int y){ if (x < y) x = y; }

void dfs(int u, int fa){
    for (auto v : son[u]) if (v != fa){
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}

void solve(int u, int fa){
    maxd[u] = dep[u];
    for (auto v : son[u]) if (v != fa){
        solve(v, u);
        if (maxd[v] - dep[u] > LMT){
            ans.push_back(v);
        } else {
            cmax(maxd[u], maxd[v]);
        }
    }
}

void init(int n){
    for (int i = 1; i <= n; i++)
        son[i].clear();
    dep[1] = 0;
    for (int i = 1; i <= n; i++)
        p[i] = i;
    LMT = sqrt(n);
    if (LMT * LMT < n)
        LMT++;
}

int getfa(int u){
    if (u == p[u])
        return u;
    return p[u] = getfa(p[u]);
}

int main(){
    int T; cin >> T;
    while (T--){
        cin >> n >> m, init(n);
        for (int i = 1; i <= m; i++)
            cin >> E[i].u >> E[i].v;
        for (int i = 1; i <= m; i++){
            int u = E[i].u, v = E[i].v;
            int fu = getfa(u), fv = getfa(v);
            if (fu == fv)
                continue;
            p[fu] = fv;
            son[u].push_back(v);
            son[v].push_back(u);
        }
        dfs(1, 0), solve(1, 0);
        if (ans.size() > LMT){
            puts("-1");
        } else {   
            cout << ans.size() << '\n';
            for (int i = 0, si = ans.size(); i < si; i++)
                cout << ans[i] << (i == si - 1 ? '\n' : ' ');
        }
    }
    return 0;
}
/*
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
*/

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 2ms

memory: 9584kb

input:

output:

result:

ok correct (2 test cases)

Test #2:

score: -100

Wrong Answer

time: 13ms

memory: 9716kb

input:

output:

2
11 6
2
11 6
3
11 6 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
-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
-...

result:

wrong answer Condition failed: "getMaxBfsDist(n, subset) <= csqrtn" (test case 1)