結果
| 問題 |
No.2618 除霊
|
| コンテスト | |
| ユーザー |
 startcpp
|
| 提出日時 | 2022-02-06 17:15:14 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 515 ms / 2,000 ms |
| コード長 | 9,647 bytes |
| コンパイル時間 | 1,398 ms |
| コンパイル使用メモリ | 109,764 KB |
| 実行使用メモリ | 43,176 KB |
| 最終ジャッジ日時 | 2024-06-28 22:29:53 |
| 合計ジャッジ時間 | 23,819 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 43 |
コンパイルメッセージ
In member function 'void FastSolver::add_near(int)',
inlined from 'virtual std::vector<int> FastSolver::solve(Testcase&)' at main.cpp:407:14:
main.cpp:338:21: warning: 'x' may be used uninitialized [-Wmaybe-uninitialized]
338 | int bfs_v = to_bfs[v];
| ^~~~~
main.cpp: In member function 'virtual std::vector<int> FastSolver::solve(Testcase&)':
main.cpp:398:37: note: 'x' was declared here
398 | int x;
| ^
ソースコード
//3解法間のストレステスト
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <random>
using namespace std;
mt19937 mt(252521); //乱数生成器, メルセンヌ・ツイスタ
//Union Find Tree
struct UF {
int n;
vector<int> par;
int merge_cnt;
void init(int n) {
this->n = n;
par.resize(n);
for (int i = 0; i < n; i++) {
par[i] = i;
}
merge_cnt = 0;
}
int root(int x) {
if (par[x] == x) { return x; }
return par[x] = root(par[x]);
}
bool same(int x, int y) { return root(x) == root(y); }
void merge(int x, int y) {
x = root(x);
y = root(y);
if (x != y) {
par[x] = y;
merge_cnt++;
}
}
};
//テストケース構造体
class Testcase {
private:
vector<int> a, b;
public:
int n;
vector<vector<int>> edge_to;
string color;
void generate(int n) {
UF uf;
uf.init(n);
edge_to.resize(n);
this->n = n;
while (uf.merge_cnt < n - 1) {
int u = mt() % n;
int v = mt() % n;
if (uf.same(u, v) == false) {
uf.merge(u, v);
a.push_back(u);
b.push_back(v);
edge_to[u].push_back(v);
edge_to[v].push_back(u);
}
}
for (int i = 0; i < n; i++) {
if (mt() % 100 < 50) {
color += 'b';
}
else {
color += 'w';
}
}
}
void input() {
cin >> n;
edge_to.resize(n);
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
a--; b--;
edge_to[a].push_back(b);
edge_to[b].push_back(a);
}
int m; cin >> m;
color = "";
for (int i = 0; i < n; i++) color += 'w';
for (int i = 0; i < m; i++) {
int v; cin >> v; v--;
color[v] = 'b';
}
}
void print() {
cout << n << endl;
for (int i = 0; i < n - 1; i++) {
cout << a[i] << " " << b[i] << endl;
}
cout << color << endl;
}
};
//Solverの基底クラス
class Solver {
protected:
int n;
vector<int> edge_to[200000];
string color;
void input(Testcase &testcase) {
n = testcase.n;
for (int i = 0; i < n; i++) {
edge_to[i] = testcase.edge_to[i];
}
color = testcase.color;
}
virtual vector<int> solve(Testcase &testcase) = 0;
};
//ナイーブ解1：O(N^2)
class NaiveSolver1 : public Solver {
private:
vector<int> operate(int v) {
vector<int> blacks;
if (color[v] == 'b') {
blacks.push_back(v);
}
for (int nv : edge_to[v]) { //vの隣接頂点nv
if (color[nv] == 'b') {
blacks.push_back(nv);
}
}
for (int b : blacks) {
color[b] = 'w';
}
return blacks;
}
bool is_danger(int v) {
if (color[v] == 'b') { return true; }
for (int nv : edge_to[v]) {
if (color[nv] == 'b') { return true; }
}
return false;
}
int calc() {
int ret = 0;
for (int v = 0; v < n; v++) { //頂点vについて危険かを調べる
if (is_danger(v)) {
ret++;
}
}
return ret;
}
void revert(vector<int> change_vs) {
for (int v : change_vs) {
color[v] = 'b';
}
}
public:
vector<int> solve(Testcase &testcase) {
input(testcase);
vector<int> ans;
for (int v = 0; v < n; v++) {
vector<int> change_vs = operate(v); //色を変更した頂点リストを返す
ans.push_back(calc());
revert(change_vs);
}
return ans;
}
};
//ナイーブ解2: O(N^2), ランダムグラフのとき高速
class NaiveSolver2 : public Solver {
private:
int cnt_black[200000]; //cnt_black[v] = 頂点v自身・vの隣接頂点のうち黒であるものの個数
int safe_cnt; //safe_cnt = cnt_black[v]が0であるような頂点vの個数
void calc_init() {
safe_cnt = 0;
for (int v = 0; v < n; v++) {
cnt_black[v] = 0;
if (color[v] == 'b') {
cnt_black[v]++;
}
for (int nv : edge_to[v]) {
if (color[nv] == 'b') {
cnt_black[v]++;
}
}
if (cnt_black[v] == 0) {
safe_cnt++;
}
}
}
vector<int> operate(int v) {
vector<int> blacks;
if (color[v] == 'b') {
blacks.push_back(v);
}
for (int nv : edge_to[v]) {
if (color[nv] == 'b') {
blacks.push_back(nv);
}
}
for (int u : blacks) { //頂点uについて、uから距離1以内の頂点xのcnt_black[x]を1減らす
cnt_black[u]--;
if (cnt_black[u] == 0) { safe_cnt++; }
for (int x: edge_to[u]) {
cnt_black[x]--;
if (cnt_black[x] == 0) { safe_cnt++; }
}
}
return blacks;
}
void revert(vector<int> change_vs) {
for (int v : change_vs) {
if (cnt_black[v] == 0) { safe_cnt--; }
cnt_black[v]++;
for (int x : edge_to[v]) {
if (cnt_black[x] == 0) { safe_cnt--; }
cnt_black[x]++;
}
}
}
public:
vector<int> solve(Testcase &testcase) {
input(testcase);
calc_init();
vector<int> ans;
for (int v = 0; v < n; v++) {
vector<int> change_vs = operate(v);
ans.push_back(n - safe_cnt);
revert(change_vs);
}
return ans;
}
};
//想定解: O(N), デバッグ済み
class FastSolver : public Solver {
private:
int black[200000]; //black[v] = vと隣接する黒頂点の個数
int to_bfs[200000];
int parent_bfs[200000];
int child_bfs_l[200000], child_bfs_r[200000]; //[l, r]
int safe_bfs[200001]; //safe_bfs[bfsId] = BFS順序でbfsId番の頂点について操作をおこなった場合の、危険でない頂点の個数
void init_member() {
for (int i = 0; i < n; i++) {
black[i] = 0;
to_bfs[i] = 0;
parent_bfs[i] = 0;
child_bfs_l[i] = 0;
child_bfs_r[i] = 0;
safe_bfs[i] = 0;
}
safe_bfs[n] = 0;
}
void bfs(int root_v) {
vector<bool> used(n, false);
queue<int> que;
int t = 0;
for (int bfs_v = 0; bfs_v < n; bfs_v++) {
parent_bfs[bfs_v] = -1;
child_bfs_l[bfs_v] = -1;
child_bfs_r[bfs_v] = -1;
}
to_bfs[root_v] = t;
t++;
que.push(root_v);
used[root_v] = true;
while (!que.empty()) {
int v = que.front();
que.pop();
for (int nv : edge_to[v]) {
if (used[nv]) { continue; }
to_bfs[nv] = t;
parent_bfs[t] = to_bfs[v];
if (child_bfs_l[to_bfs[v]] == -1) { child_bfs_l[to_bfs[v]] = t; } //最初見る子のbfsIdになる
child_bfs_r[to_bfs[v]] = t; //最後見る子のbfsIdになる
t++;
que.push(nv);
used[nv] = true;
}
}
}
//safe_bfs[l, r) += 1, を階差数列上でおこなう
void add(int l, int r) {
if (debug_flag) {
printf("safe_bfs[%d, %d] += 1\n", l, r);
}
safe_bfs[l]++;
safe_bfs[r + 1]--;
}
void add_near(int v) {
int bfs_v = to_bfs[v];
int l = child_bfs_l[bfs_v];
int r = child_bfs_r[bfs_v];
int p = parent_bfs[bfs_v];
//v自身
add(bfs_v, bfs_v);
//vの子[l, r] (vが葉でないとき)
if (l != -1) {
add(l, r);
}
//vの親（vが根でないとき）
if (p != -1) {
add(p, p);
}
}
public:
bool debug_flag;
FastSolver() { debug_flag = false; }
vector<int> solve(Testcase &testcase) {
input(testcase);
init_member();
for (int v = 0; v < n; v++) {
for (int nv : edge_to[v]) {
if (color[nv] == 'b') {
black[v]++;
}
}
}
bfs(0);
if (debug_flag) {
cout << " id | to_bfs, parent_bfs, child_bfs_l, child_bfs_r" << endl;
cout << "--------------------------------------------------" << endl;
for (int v = 0; v < n; v++) {
printf("%3d | %6d, %10d, %11d, %11d\n", v, to_bfs[v], parent_bfs[to_bfs[v]], child_bfs_l[to_bfs[v]], child_bfs_r[to_bfs[v]]);
}
}
for (int v = 0; v < n; v++) { //頂点vが安全になる操作uをカウントアップ
if (debug_flag) {
printf("\n");
printf("black[%d] = %d, color[%d] = %c\n", v, black[v], v, color[v]);
}
if (black[v] == 0) {
if (color[v] == 'w') { //u: 全頂点, imos法で区間[0, n)に加算
add(0, n - 1);
}
else {
add_near(v); //v自身とvの隣接頂点に加算
}
}
else if (black[v] == 1) {
int x;
for (int nv : edge_to[v]) { //v=0,..,Nにおけるループ回数の和は次数の和 = 2N - 2.
if (color[nv] == 'b') {
x = nv;
break;
}
}
if (color[v] == 'w') {
add_near(x); //x自身とxの隣接頂点に加算、ここの高速化がデカい！
}
else {
int bfs_x = to_bfs[x];
int bfs_v = to_bfs[v];
add(bfs_x, bfs_x);
add(bfs_v, bfs_v);
}
}
else { //操作uで頂点vを安全にするには、u = vとするしかない！
int bfs_v = to_bfs[v];
add(bfs_v, bfs_v);
}
}
//累積和を取る
for (int i = 0; i < n; i++) {
safe_bfs[i + 1] += safe_bfs[i];
}
//答えを出力する
if (debug_flag) {
puts("");
}
vector<int> ans;
for (int v = 0; v < n; v++) {
if (debug_flag) {
printf("safe_bfs[%d] = %d\n", v, safe_bfs[v]);
}
int bfs_v = to_bfs[v];
ans.push_back(n - safe_bfs[bfs_v]);
}
return ans;
}
};
NaiveSolver1 solver1;
NaiveSolver2 solver2;
FastSolver solver3;
bool stress_test(int caseNum, int N, Testcase &return_case) {
for (int T = 0; T < caseNum; T++) {
int n = N;
Testcase testcase;
testcase.generate(n);
vector<int> ans1 = solver1.solve(testcase);
vector<int> ans3 = solver3.solve(testcase);
if (ans1 != ans3) {
cout << "Wrong Answer[" << T << "]" << endl;
cout << "Testcase (0-idx):" << endl;
testcase.print();
cout << endl;
cout << "Different Answer (0-idx):" << endl;
for (int i = 0; i < n; i++) {
if (ans1[i] != ans3[i]) {
cout << i << " : " << ans1[i] << ", " << ans3[i] << endl;
}
}
return_case = testcase;
return true;
}
}
cout << "Accepted" << endl;
return false;
}
int main() {
/*Testcase testcase;
bool is_wrong = stress_test(1000, 15, testcase);
if (is_wrong) {
solver3.debug_flag = true;
solver3.solve(testcase);
}*/
Testcase testcase;
testcase.input();
vector<int> ans = solver3.solve(testcase);
for (int i = 0; i < ans.size(); i++) cout << ans[i] << endl;
}