結果

問題 No.2618 除霊
ユーザー startcppstartcpp
提出日時 2022-02-06 17:15:14
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 576 ms / 2,000 ms
コード長 9,647 bytes
コンパイル時間 1,959 ms
コンパイル使用メモリ 106,876 KB
実行使用メモリ 43,996 KB
最終ジャッジ日時 2023-09-11 07:58:37
合計ジャッジ時間 31,488 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
22,952 KB
testcase_01 AC 9 ms
23,092 KB
testcase_02 AC 9 ms
22,940 KB
testcase_03 AC 9 ms
22,960 KB
testcase_04 AC 9 ms
22,940 KB
testcase_05 AC 9 ms
22,952 KB
testcase_06 AC 513 ms
41,064 KB
testcase_07 AC 505 ms
40,900 KB
testcase_08 AC 548 ms
41,388 KB
testcase_09 AC 536 ms
40,892 KB
testcase_10 AC 553 ms
41,576 KB
testcase_11 AC 496 ms
41,476 KB
testcase_12 AC 576 ms
41,144 KB
testcase_13 AC 469 ms
43,688 KB
testcase_14 AC 524 ms
42,980 KB
testcase_15 AC 466 ms
43,080 KB
testcase_16 AC 478 ms
43,220 KB
testcase_17 AC 519 ms
43,996 KB
testcase_18 AC 522 ms
42,932 KB
testcase_19 AC 491 ms
43,020 KB
testcase_20 AC 466 ms
43,368 KB
testcase_21 AC 498 ms
42,064 KB
testcase_22 AC 530 ms
43,560 KB
testcase_23 AC 494 ms
42,744 KB
testcase_24 AC 484 ms
43,232 KB
testcase_25 AC 531 ms
42,888 KB
testcase_26 AC 520 ms
42,548 KB
testcase_27 AC 479 ms
42,584 KB
testcase_28 AC 478 ms
43,632 KB
testcase_29 AC 521 ms
43,080 KB
testcase_30 AC 541 ms
43,360 KB
testcase_31 AC 557 ms
40,500 KB
testcase_32 AC 521 ms
41,116 KB
testcase_33 AC 532 ms
40,860 KB
testcase_34 AC 512 ms
39,992 KB
testcase_35 AC 533 ms
40,560 KB
testcase_36 AC 563 ms
41,616 KB
testcase_37 AC 530 ms
40,312 KB
testcase_38 AC 562 ms
41,644 KB
testcase_39 AC 569 ms
40,932 KB
testcase_40 AC 547 ms
40,936 KB
testcase_41 AC 563 ms
41,100 KB
testcase_42 AC 573 ms
41,120 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
メンバ関数 ‘void FastSolver::add_near(int)’ 内,
    inlined from ‘virtual std::vector<int> FastSolver::solve(Testcase&)’ at main.cpp:407:14:
main.cpp:338:21: 警告: ‘x’ may be used uninitialized [-Wmaybe-uninitialized]
  338 |                 int bfs_v = to_bfs[v];
      |                     ^~~~~
main.cpp: メンバ関数 ‘virtual std::vector<int> FastSolver::solve(Testcase&)’ 内:
main.cpp:398:37: 備考: ‘x’ はここで定義されています
  398 |                                 int x;
      |                                     ^

ソースコード

diff # 

//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;
}
0