結果

問題 No.2618 除霊
コンテスト
ユーザー startcpp
提出日時 2022-10-02 11:12:55
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 597 ms / 2,000 ms
コード長 1,351 bytes
コンパイル時間 822 ms
コンパイル使用メモリ 70,272 KB
実行使用メモリ 16,716 KB
最終ジャッジ日時 2024-12-24 21:30:46
合計ジャッジ時間 27,348 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

int n;
vector<int> et[200000];	//edge to
int m;
bool ghost[200000];		//ghost[v]     = 頂点vにおばけがいるか
int safe_cnt[200000];	//safe_cnt[u]  = 頂点uで除霊をおこなったときに、魔の手から逃れられる街の数
int all_add;			//add_add      = 全頂点uについてsafe_cnt[u] += 1する回数
int add_query[200000];	//add_query[v] = 頂点vから距離1以内の頂点uについてsafe_cnt[u]++する操作をおこなう回数

int main() {
	int i, j;
	
	cin >> n;
	rep(i, n - 1) {
		int a, b; cin >> a >> b; a--; b--;
		et[a].push_back(b);
		et[b].push_back(a);
	}
	cin >> m;
	rep(i, m) { int v; cin >> v; v--; ghost[v] = true; }
	
	rep(i, n) {
		int black = 0, black_v = -1;
		rep(j, et[i].size()) {
			if (ghost[et[i][j]]) {
				black++;
				black_v = et[i][j];
			}
		}
		
		if (black >= 2) { safe_cnt[i]++; }
		if (black == 1) {
			if (ghost[i]) { safe_cnt[i]++; safe_cnt[black_v]++; }
			else { add_query[black_v]++; }
		}
		if (black == 0) {
			if (ghost[i]) { add_query[i]++; }
			else { all_add++; }
		}
	}
	
	rep(i, n) {
		safe_cnt[i] += add_query[i];
		rep(j, et[i].size()) { safe_cnt[et[i][j]] += add_query[i]; }
		safe_cnt[i] += all_add;
	}
	
	rep(i, n) { cout << n - safe_cnt[i] << endl; }
	return 0;
}
0