oj.uz

Submission #100910

# Submission time Handle Problem Language Result Execution time Memory
100910 2019-03-15T05:19:13 Z E869120 Synchronization (JOI13_synchronization) C++14
100 / 100
 6375 ms 40968 KB 
// クエリ平方分割 + bitset の　(N^1.5 + N^2 / 64) で満点を狙う。

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

const int Backet = 700;

int N, M, A[200009], B[200009], X[200009], D1[200009], D2[200009], popcnt[1 << 22];
int num[200009], col[200009], colnum[200009], cnts, cntv;
bool used[200009], real_used[200009], vertex_used[200009], v[200009];
vector<int> G1[200009], G2[200009];

unsigned long long ptr[300009];

void init_state() {
	for (int i = 1; i <= N; i++) { col[i] = 0; colnum[i] = 0; }
	for (int i = 1; i <= N; i++) { vertex_used[i] = false; G1[i].clear(); G2[i].clear(); }
}

void dfs1(int pos) {
	col[pos] = cnts;
	for (int i : G1[pos]) { if (col[i] == 0) dfs1(i); }
}

void dfs2(int pos, int rev) {
	colnum[pos] = rev;
	for (int i : G2[pos]) { if (colnum[i] != rev) dfs2(i, rev); }
}

void solve(int l, int r) {
	// 最初に、グラフに関係ない辺を貼り、連結成分ごとに分ける
	cnts = 0; init_state();
	for (int i = 1; i <= N - 1; i++) real_used[i] = used[i];
	for (int i = l; i <= r; i++) { real_used[X[i]] = false; vertex_used[A[X[i]]] = true; vertex_used[B[X[i]]] = true; }
	for (int i = 1; i <= N - 1; i++) { if (real_used[i] == true) { G1[A[i]].push_back(B[i]); G1[B[i]].push_back(A[i]); } }
	for (int i = 1; i <= N; i++) { if (col[i] == 0 && vertex_used[i] == true) { cnts++; dfs1(i); } }
	for (int i = 1; i <= N; i++) colnum[col[i]] = num[i];

	//cout << "col = {"; for (int i = 1; i <= N; i++) { if (i >= 2) cout << ", "; cout << col[i]; } cout << "}" << endl;
	//cout << "colnum = {"; for (int i = 1; i <= cnts; i++) { if (i >= 2) cout << ", "; cout << colnum[i]; } cout << "}" << endl;

	// 次に、各クエリを処理する
	for (int i = l; i <= r; i++) {
		int pos = X[i];
		if (used[pos] == false) {
			// 連結する場合
			int A1 = colnum[col[A[pos]]], A2 = colnum[col[B[pos]]];
			for (int j = 1; j <= cnts; j++) { if (colnum[j] == A2) colnum[j] = A1; }
			used[pos] = true; D1[i] = A1; D2[i] = A2; v[i] = false;
		}
		else if (used[pos] == true) {
			// 分離する場合
			used[pos] = false;
			for (int j = 1; j <= cnts; j++) G2[j].clear();
			for (int j = l; j <= r; j++) {
				if (used[X[j]] == false) continue;
				int p1 = col[A[X[j]]], p2 = col[B[X[j]]];
				G2[p1].push_back(p2); G2[p2].push_back(p1);
			}
			int A1 = colnum[col[A[pos]]];
			cntv++; dfs2(col[B[pos]], cntv);
			D1[i] = A1; D2[i] = cntv; v[i] = true;
		}
		//for (int j = 1; j <= N; j++) cout << colnum[col[j]] << " "; cout << endl;
	}

	// 最後に、全体を更新する
	for (int i = 1; i <= N; i++) { if (col[i] >= 1) num[i] = colnum[col[i]]; }
	//for (int i = 1; i <= N; i++) cout << num[i] << " "; cout << endl;
}

void init() {
	for (int i = 0; i < (1 << 22); i++) popcnt[i] = __builtin_popcount(i);
}

int ans[100009];

int main() {
	//FILE *in = freopen("in1.txt", "r", stdin);
	//FILE *out = freopen("out1.txt", "w", stdout);
	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);
	}
	//for (int i = 1; i <= N; i++) cout << i << ": D1 = " << D1[i] << ", D2 = " << D2[i] << endl;

	// ビットセットパート
	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] += (1ULL << (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

synchronization.cpp: In function 'int main()':
synchronization.cpp:82: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:84: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:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &X[i]);
   ~~~~~^~~~~~~~~~~~~
synchronization.cpp:122:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &cc);
   ~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 26232 KB Output is correct
2 Correct 44 ms 26232 KB Output is correct
3 Correct 46 ms 26232 KB Output is correct
4 Correct 37 ms 26232 KB Output is correct
5 Correct 45 ms 26252 KB Output is correct
6 Correct 54 ms 26360 KB Output is correct
7 Correct 141 ms 27128 KB Output is correct
8 Correct 154 ms 27176 KB Output is correct
9 Correct 149 ms 27252 KB Output is correct
10 Correct 6081 ms 35844 KB Output is correct
11 Correct 6375 ms 35828 KB Output is correct
12 Correct 5702 ms 36124 KB Output is correct
13 Correct 5461 ms 35924 KB Output is correct
14 Correct 3071 ms 34284 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2045 ms 37508 KB Output is correct
2 Correct 2012 ms 37428 KB Output is correct
3 Correct 1275 ms 37216 KB Output is correct
4 Correct 1129 ms 37092 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 26244 KB Output is correct
2 Correct 36 ms 26232 KB Output is correct
3 Correct 39 ms 26236 KB Output is correct
4 Correct 38 ms 26232 KB Output is correct
5 Correct 39 ms 26232 KB Output is correct
6 Correct 46 ms 26360 KB Output is correct
7 Correct 153 ms 27380 KB Output is correct
8 Correct 5465 ms 36148 KB Output is correct
9 Correct 5918 ms 36508 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5773 ms 36028 KB Output is correct
2 Correct 1171 ms 37700 KB Output is correct
3 Correct 1224 ms 37760 KB Output is correct
4 Correct 1218 ms 37752 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 26280 KB Output is correct
2 Correct 42 ms 26184 KB Output is correct
3 Correct 40 ms 26232 KB Output is correct
4 Correct 36 ms 26232 KB Output is correct
5 Correct 44 ms 26232 KB Output is correct
6 Correct 147 ms 27260 KB Output is correct
7 Correct 5799 ms 36500 KB Output is correct
8 Correct 5962 ms 39176 KB Output is correct
9 Correct 5556 ms 38668 KB Output is correct
10 Correct 3018 ms 37188 KB Output is correct
11 Correct 2143 ms 40968 KB Output is correct
12 Correct 2137 ms 40848 KB Output is correct
13 Correct 1323 ms 40084 KB Output is correct