Submission #100895

#	Time	Username	Problem	Language	Result	Execution time	Memory
100895		E869120	Synchronization (JOI13_synchronization)	C++14	0 / 100	8098 ms	33424 KiB

synchronization

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

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

const int Backet = 700;

int N, M, A[100009], B[100009], X[200009], D1[200009], D2[200009], popcnt[1 << 22];
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]];
}

void init() {
	for (int i = 0; i < (1 << 22); i++) popcnt[i] = __builtin_popcount(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; init();
	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 <= N; j++) {
			unsigned long long E = ptr[num[j]];
			ans[j] += popcnt[E & 4194303]; E >>= 22;
			ans[j] += popcnt[E & 4194303]; E >>= 22;
			ans[j] += popcnt[E];
		}
	}
	for (int j = 1; j <= Q; j++) {
		int cc;
		scanf("%d", &cc);
		printf("%d\n", ans[cc]);
	}
	return 0;
}

Compilation message (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:96: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:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &A[i], &B[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &X[i]);
   ~~~~~^~~~~~~~~~~~~
synchronization.cpp:135:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &cc);
   ~~~~~^~~~~~~~~~~

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