oj.uz

답안 #100906

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
100906 2019-03-15T04:43:22 Z E869120 동기화 (JOI13_synchronization) C++14
0 / 100
 8000 ms 27640 KB 
// クエリ平方分割 + bitset の　(N^1.5 + N^2 / 64) で満点を狙う。

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

const int Backet = 1;

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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 26232 KB Output is correct
2 Correct 38 ms 26232 KB Output is correct
3 Correct 39 ms 26232 KB Output is correct
4 Correct 40 ms 26232 KB Output is correct
5 Correct 53 ms 26364 KB Output is correct
6 Correct 54 ms 26236 KB Output is correct
7 Correct 4040 ms 27308 KB Output is correct
8 Correct 3818 ms 27332 KB Output is correct
9 Correct 3930 ms 27328 KB Output is correct
10 Execution timed out 8055 ms 13520 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8073 ms 13528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 26240 KB Output is correct
2 Correct 37 ms 26236 KB Output is correct
3 Correct 39 ms 26232 KB Output is correct
4 Correct 46 ms 26232 KB Output is correct
5 Correct 37 ms 26232 KB Output is correct
6 Correct 82 ms 26408 KB Output is correct
7 Correct 3498 ms 27620 KB Output is correct
8 Execution timed out 8047 ms 13960 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8093 ms 13596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 26236 KB Output is correct
2 Correct 51 ms 26232 KB Output is correct
3 Correct 43 ms 26232 KB Output is correct
4 Correct 40 ms 26252 KB Output is correct
5 Correct 62 ms 26360 KB Output is correct
6 Correct 4040 ms 27640 KB Output is correct
7 Execution timed out 8079 ms 13696 KB Time limit exceeded
8 Halted 0 ms 0 KB -