제출 #100891

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
100891		E869120	Synchronization (JOI13_synchronization)	C++14	0 / 100	8042 ms	17180 KiB

synchronization

// クエリ平方分割 + bitset の　(N^1.5 + N^2 / 64) で満点を狙う。

#include <bits/stdc++.h>
using namespace std;

const int Backet = 500;

int N, M, A[100009], B[100009], X[200009], D1[200009], D2[200009];
int num[100009], col[100009], colnum[100009], cnts, cntv;
bool used[100009], used2[100009], used3[100009], v[100009];
vector<int> G1[100009], G2[100009];

unsigned long long ptr[300009];

void dfs(int pos) {
	col[pos] = cnts;
	for (int i : G1[pos]) {
		if (col[i] >= 1) continue;
		dfs(i);
	}
}

void dfs1(int pos, int rev) {
	colnum[pos] = rev; used3[pos] = true;
	for (int i : G2[pos]) {
		if (used3[i] == true) continue;
		dfs1(i, rev);
	}
}

void solve(int l, int r) {
	for (int i = 1; i <= N; i++) { col[i] = 0; colnum[i] = 0; G1[i].clear(); }
	for (int i = 1; i <= N - 1; i++) used2[i] = used[i];
	for (int i = l; i <= r; i++) used2[X[i]] = false;
	
	for (int i = 1; i <= N - 1; i++) {
		if (used2[i] == false) continue;
		G1[A[i]].push_back(B[i]);
		G1[B[i]].push_back(A[i]);
	}
	
	cnts = 0;
	
	for (int i = 1; i <= N; i++) {
		if (col[i] >= 1) continue;
		cnts++; dfs(i);
	}
	for (int i = 1; i <= N; i++) colnum[col[i]] = num[i];
	
	vector<int>E;
	for (int i = l; i <= r; i++) { E.push_back(col[A[X[i]]]); E.push_back(col[B[X[i]]]); }
	sort(E.begin(), E.end()); E.erase(unique(E.begin(), E.end()), E.end());
	
	for (int i = l; i <= r; i++) {
		for (int j = 0; j < E.size(); j++) { used3[E[j]] = false; G2[E[j]].clear(); }
		
		// グラフに現在の辺を貼る
		for (int j = l; j <= i; j++) {
			bool e = used[X[j]]; if (X[j] == X[i]) e ^= true;
			if (e == false) continue;
			
			int pos = X[j];
			G2[col[A[pos]]].push_back(col[B[pos]]);
			G2[col[B[pos]]].push_back(col[A[pos]]);
		}
		
		int pos = X[i];
		if (used[pos] == false) {
			// 結合する場合 : D1 と D2 を結合して D1 にする
			D1[i] = colnum[col[A[pos]]];
			D2[i] = colnum[col[B[pos]]];
			dfs1(col[A[pos]], D1[i]);
			v[i] = false;
		}
		if (used[pos] == true) {
			// 分離する場合: D1 を D2 にコピーする
			D1[i] = colnum[col[A[pos]]];
			D2[i] = cntv + 1; cntv++;
			dfs1(col[B[pos]], cntv);
			v[i] = true;
		}
		used[pos] ^= true;
	}
	
	for (int i = 1; i <= N; i++) num[i] = colnum[col[i]];
}

int ans[100009];

int main() {
	int Q;
	scanf("%d%d%d", &N, &M, &Q);
	for (int i = 1; i <= N - 1; i++) scanf("%d%d", &A[i], &B[i]);
	for (int i = 1; i <= M; i++) scanf("%d", &X[i]);
	for (int i = 1; i <= N; i++) num[i] = i;
	
	cntv = N;
	
	// クエリ平方分割パート
	for (int i = 1; i <= M; i += Backet) {
		int L = i, R = i + Backet - 1; if (R > M) R = M;
		
		solve(L, R);
	}
	
	// ビットセットパート
	int BASE = 64;
	for (int i = 1; i <= N; i += BASE) {
		int L = i, R = i + (BASE - 1); if (R >= N) R = N;
		for (int j = 1; j <= cntv; j++) ptr[j] = 0;
		for (int j = L; j <= R; j++) ptr[j] += (1LL << (j - L));
		
		for (int j = 1; j <= M; j++) {
			if (v[j] == false) ptr[D1[j]] |= ptr[D2[j]];
			if (v[j] == true) ptr[D2[j]] = ptr[D1[j]];
		}
		
		for (int j = 1; j <= M; j++) ans[j] += __builtin_popcountll(ptr[num[j]]);
	}
	for (int j = 1; j <= Q; j++) {
		int cc; scanf("%d", &cc);
		printf("%d\n", ans[cc]);
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

synchronization.cpp: In function 'void solve(int, int)':
synchronization.cpp:55:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < E.size(); j++) { used3[E[j]] = false; G2[E[j]].clear(); }
                   ~~^~~~~~~~~~
synchronization.cpp: In function 'int main()':
synchronization.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:93:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= N - 1; i++) scanf("%d%d", &A[i], &B[i]);
                                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:94:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= M; i++) scanf("%d", &X[i]);
                               ~~~~~^~~~~~~~~~~~~
synchronization.cpp:121:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int cc; scanf("%d", &cc);
           ~~~~~^~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40