QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#136420	#6634. Central Subset	NightW0lf^#	RE	1ms	3560kb	C++23	2.6kb	2023-08-08 18:36:37	2023-08-08 18:36:40

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-08 18:36:40]
评测

测评结果：RE
用时：1ms
内存：3560kb

查看

[2023-08-08 18:36:37]
提交

answer

#include <bits/stdc++.h>

#define IO	       { ios_base::sync_with_stdio(false); cin.tie(0); }

using namespace std;
#define int long long 

int lim;
int n, m;
vector<vector<int>> adj;
vector<int> subtree_size;
vector<bool> is_removed;
vector<int> ans;

int get_subtree_size(int node, int parent = -1) {
	subtree_size[node] = 1;
	for (int child : adj[node]) {
		if (child == parent || is_removed[child]) { continue; }
		subtree_size[node] += get_subtree_size(child, node);
	}
	return subtree_size[node];
}

int get_centroid(int node, int tree_size, int parent = -1) {
	for (int child : adj[node]) {
		if (child == parent || is_removed[child]) { continue; }
		if (subtree_size[child] * 2 > tree_size) {
			return get_centroid(child, tree_size, node);
		}
	}
	return node;
}

void build_centroid_decomp(int node = 0) {
    int sz = get_subtree_size(node);
    if (sz <= lim and node != 0) return;
	int centroid = get_centroid(node, sz);

	ans.push_back(centroid);

	is_removed[centroid] = true;

	for (int child : adj[centroid]) {
		if (is_removed[child]) { continue; }
		build_centroid_decomp(child);
	}
}


vector<vector<int>> adj2;
vector<bool> vis;

void dfs(int node) {
    vis[node] = 1;
    for (int v: adj2[node]) {
        if (!vis[v]) {
            adj[v].push_back(node);
            adj[node].push_back(v);
            dfs(v);
        }
    }
}

void solve() {
    cin >> n >> m;
    for (int i=1; ;i++) {
        if (i*i >= n) {
            lim = i;
            break;
        }
    }
    
    adj.clear();
    adj2.clear();
    adj.resize(n+100);
    adj2.resize(n+100);
    subtree_size.assign(n+100, 0);
    vis.assign(n+100, 0);
    is_removed.assign(n+100, 0);

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
        adj2[a].push_back(b);
        adj2[b].push_back(a);
	}

    dfs(0);
    ans.clear();

    build_centroid_decomp(0);

    assert(ans.size() <= lim);

    vector<int> gg(n + 1);
    queue<int> q;
    for(auto x: ans) {
        gg[x] = 1;
        q.push(x);
    }
    while(!q.empty()) {
        int temp = q.front();
        //assert(gg[temp] - 1 <= lim);
        q.pop();
        for(auto x: adj[temp]) {
            if(gg[x] == 0) {
                gg[x] = gg[temp] + 1;
                q.push(x);
            }
        }
    }

    cout << ans.size() << endl;
    
    for (int x: ans) {
        cout << x + 1 << " ";
    }
    cout << endl;
}

signed main() {
    IO;
    int t;
    cin >> t;
    while(t--) {
        solve();
    }
}
/*
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++23

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 3560kb

input:

output:

result:

ok correct (2 test cases)

Test #2:

score: -100

Dangerous Syscalls

input:

output: