oj.uz

Submission #100907

# Submission time Handle Problem Language Result Execution time Memory
100907 2019-03-15T04:44:46 Z E869120 Synchronization (JOI13_synchronization) C++14
50 / 100
 6753 ms 38392 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 <= i; 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 38 ms 26232 KB Output is correct
2 Correct 37 ms 26240 KB Output is correct
3 Correct 41 ms 26232 KB Output is correct
4 Correct 36 ms 26232 KB Output is correct
5 Correct 52 ms 26232 KB Output is correct
6 Correct 44 ms 26232 KB Output is correct
7 Correct 111 ms 27128 KB Output is correct
8 Correct 137 ms 27200 KB Output is correct
9 Correct 113 ms 27128 KB Output is correct
10 Correct 5474 ms 35972 KB Output is correct
11 Correct 6753 ms 36264 KB Output is correct
12 Correct 5326 ms 36316 KB Output is correct
13 Correct 4960 ms 36100 KB Output is correct
14 Correct 2933 ms 34532 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2122 ms 37568 KB Output is correct
2 Correct 1976 ms 37496 KB Output is correct
3 Correct 1286 ms 37140 KB Output is correct
4 Correct 1385 ms 37624 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 26232 KB Output is correct
2 Correct 40 ms 26232 KB Output is correct
3 Correct 40 ms 26232 KB Output is correct
4 Correct 39 ms 26232 KB Output is correct
5 Correct 37 ms 26260 KB Output is correct
6 Incorrect 50 ms 26360 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5457 ms 36344 KB Output is correct
2 Correct 1350 ms 38136 KB Output is correct
3 Correct 1286 ms 38392 KB Output is correct
4 Correct 1228 ms 38140 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 26232 KB Output is correct
2 Correct 37 ms 26212 KB Output is correct
3 Correct 40 ms 26196 KB Output is correct
4 Correct 39 ms 26240 KB Output is correct
5 Incorrect 42 ms 26360 KB Output isn't correct
6 Halted 0 ms 0 KB -