QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#330506#8055. Balanceucup-team1198#WA 110ms13032kbC++175.2kb2024-02-17 16:33:192024-02-17 16:33:19

Judging History

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

  • [2024-02-17 16:33:19]
  • 评测
  • 测评结果:WA
  • 用时:110ms
  • 内存:13032kb
  • [2024-02-17 16:33:19]
  • 提交

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

const int MAXN = 200200;

vector<pair<int, int>> G1[MAXN];

int used[MAXN];
int tin[MAXN];
int tup[MAXN];
bool is_bridge[MAXN];
int ttime = 0;

void dfs1(int v, int p) {
	++ttime;
	used[v] = 1;
	tin[v] = ttime;
	tup[v] = ttime;
	for (auto [u, i] : G1[v]) {
		if (i == p)
			continue;
		if (used[u] == 0) {
			dfs1(u, i);
			if (tup[u] > tin[v]) {
				is_bridge[i] = true;
			}
			tup[v] = min(tup[v], tup[u]);
		} else if (used[u] == 1) {
			tup[v] = min(tup[v], tin[u]);
		}
	}
	used[v] = 2;
}

int id[MAXN];
int w[MAXN];

void dfs2(int v, int c) {
	id[v] = c;
	++w[c];
	for (auto [u, i] : G1[v]) {
		if (is_bridge[i])
			continue;
		if (id[u] == -1)
			dfs2(u, c);
	}
}

vector<int> G2[MAXN];
int sz[MAXN];
int up[MAXN];

void dfs3(int v, int p) {
	up[v] = p;
	sz[v] = w[v];
	for (int u : G2[v]) {
		if (u == p)
			continue;
		dfs3(u, v);
		sz[v] += sz[u];
	}
}

int n;

int get_or_tree_sz(int v, int u) {
	if (up[u] == v) {
		return sz[u];
	}
	return n - sz[v];
}

int total = 0;

void dfs4(int v, int p, int ban, int c, vector<int>& ans) {
	ans[v] = c;
	total += w[v];
	for (int u : G2[v]) {
		if (u == p || u == ban)
			continue;
		dfs4(u, v, ban, c, ans);
	}
}

void solve() {
	int m;
	cin >> n >> m;
	vector<pair<int, int>> edges(m);
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		--a;
		--b;
		G1[a].emplace_back(b, i);
		G1[b].emplace_back(a, i);
		edges[i] = make_pair(a, b);
	}
	map<int, int> cnt;
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		++cnt[x];
	}
	vector<pair<int, int>> cnts;
	for (auto kek : cnt)
		cnts.emplace_back(kek.second, kek.first);
	vector<int> pref_sums(cnts.size() + 1);
	for (int i = 0; i < cnts.size(); ++i)
		pref_sums[i + 1] = pref_sums[i] + cnts[i].first;

	fill(is_bridge, is_bridge + m, false);
	fill(used, used + n, 0);
	fill(w, w + n, false);
	dfs1(0, -1);
	fill(id, id + n, -1);
	int N = 0;
	for (int i = 0; i < n; ++i) {
		if (id[i] == -1) {
			dfs2(i, N);
			++N;
		}
	}

	//cerr << N << '\n';

	for (int i = 0; i < m; ++i) {
		if (is_bridge[i]) {
			auto [a, b] = edges[i];
			a = id[a];
			b = id[b];
			G2[a].emplace_back(b);
			G2[b].emplace_back(a);
			//cerr << "bridge " << a << ' ' << b << '\n';
		}
	}
	dfs3(0, -1);
	if (N == 1) {
		if (cnt.size() == 1) {
			cout << "Yes\n";
			for (int i = 0; i < n; ++i)
				cout << cnts[0].second << ' ';
			cout << '\n';
		} else {
			cout << "No\n";
		}
	} else {
		vector<pair<int, int>> Q;
		vector<int> par;
		int q_st = 0;
		vector<bool> is_leaf(N);
		for (int i = 0; i < N; ++i) {
			if (G2[i].size() == 1) {
				int v = G2[i][0];
				if (w[i] <= pref_sums[1]) {
					Q.emplace_back(i, v);
					par.emplace_back(-1);
					G2[i].clear();
				}
				is_leaf[i] = true;
			}
			sort(G2[i].begin(), G2[i].end(), [&i](int a, int b) {
				return get_or_tree_sz(i, a) < get_or_tree_sz(i, b);
			});
		}
		bool ans = false;
		while (q_st < Q.size()) {
			auto [u, v] = Q[q_st];
			++q_st;
			if (is_leaf[v])
				ans = true;

			int was_cnt = get_or_tree_sz(v, u);
			int i1 = upper_bound(pref_sums.begin(), pref_sums.end(), was_cnt) - pref_sums.begin();

			bool extract_u = false;
			while (!G2[v].empty()) {
				if (G2[v].back() == u) {
					G2[v].pop_back();
					extract_u = true;
					continue;
				}
				int nxt = G2[v].back();
				int new_cnt = get_or_tree_sz(nxt, v);
				if (pref_sums[i1] >= new_cnt) {
					Q.emplace_back(v, nxt);
					par.emplace_back(q_st - 1);
					G2[v].pop_back();
				} else {
					break;
				}
			}
			if (extract_u)
				G2[v].emplace_back(u);
		}
		if (!ans) {
			cout << "No\n";
		} else {
			cout << "Yes\n";
			int cur = q_st - 1;
			vector<int> path;
			path.emplace_back(Q[cur].second);
			while (cur != -1) {
				path.emplace_back(Q[cur].first);
				cur = par[cur];
			}
			reverse(path.begin(), path.end());
			for (int i = 0; i < N; ++i) {
				G2[i].clear();
			}
			for (int i = 0; i < m; ++i) {
				if (is_bridge[i]) {
					auto [a, b] = edges[i];
					a = id[a];
					b = id[b];
					G2[a].emplace_back(b);
					G2[b].emplace_back(a);
				}
			}
			/*cerr << "path: ";
			for (int v : path)
				cerr << v << ' ';
			cerr << '\n';*/
			total = 0;
			int cur_col = 0;
			vector<int> ans(N);
			for (int i = 0; i < path.size(); ++i) {
				dfs4(path[i], (i + 1 == path.size() ? -1 : path[i + 1]), (i ? path[i - 1] : -1), cnts[cur_col].second, ans);
				//cerr << total << ' ' << cur_col << '\n';
				if (total == pref_sums[cur_col + 1])
					++cur_col;
			}
			for (int i = 0; i < n; ++i)
				cout << ans[id[i]] << ' ';
			cout << '\n';
		}
	}

	for (int i = 0; i < n; ++i)
		G1[i].clear();
	for (int i = 0; i < N; ++i)
		G2[i].clear();
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 13008kb

input:

5
5 4
1 2
2 3
3 4
4 5
1 2 3 4 5
5 4
1 2
1 3
1 4
1 5
1 2 3 4 5
5 4
1 2
1 3
1 4
1 5
1 2 2 2 3
5 6
1 2
1 2
2 3
3 4
4 5
3 5
1 2 1 2 1
2 2
1 2
1 2
1 2

output:

Yes
5 4 3 2 1 
No
Yes
2 3 1 2 2 
Yes
2 2 1 1 1 
No

result:

ok ok (5 test cases)

Test #2:

score: -100
Wrong Answer
time: 110ms
memory: 13032kb

input:

100000
4 3
4 2
1 3
2 1
2 1 3 2
5 7
2 5
5 3
2 3
5 1
4 3
2 4
4 3
1 3 1 1 2
3 2
2 1
2 3
1 1 1
4 7
3 4
1 4
2 3
4 3
4 2
3 1
4 3
2 3 3 2
4 6
2 4
3 1
1 2
1 2
2 3
4 2
1 1 3 3
4 7
3 2
4 2
1 2
3 4
3 2
2 4
3 4
2 1 1 1
5 5
3 2
1 5
4 5
4 3
2 1
1 2 2 3 2
3 5
2 3
1 3
3 1
3 1
2 1
3 2 3
2 3
2 1
2 1
1 2
1 1
2 3
2 1
1...

output:

Yes
2 2 3 1 
Yes
1 1 1 1 1 
Yes
1 1 1 
No
No
Yes
2 1 1 1 
No
No
Yes
1 1 
Yes
1 1 
Yes
1 1 
Yes
1 1 1 1 
No
Yes
1 1 1 1 1 
Yes
1 1 1 1 1 
Yes
1 1 1 
Yes
2 1 
Yes
1 1 1 1 1 
Yes
2 1 
No
Yes
1 1 
Yes
1 1 1 
Yes
1 1 
Yes
1 1 1 1 
Yes
1 1 
Yes
2 2 2 2 2 
Yes
1 1 1 1 1 
Yes
1 1 
Yes
1 2 1 1 
No
Yes
1 1 
N...

result:

wrong answer 4-th smallest numbers are not same (test case 2)