제출 #30569

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
30569		azneye	동기화 (JOI13_synchronization)	C++14	30 / 100	5543 ms	262144 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int par[110000], x[110000], y[110000], d[310000], c[110000], t[110000], vis[110000];
vector<int> edges[110000];
vector<int> ints[110000];
vector<int> inte[110000];
vector<int> ans[110000];
int numreach[110000];
void dfs(int a){
	if(vis[a]) return;
	vis[a] = 1;
	for(int c = 0; c < edges[a].size(); c++){
		if(t[edges[a][c]]){
			if(x[edges[a][c]] != a) dfs(x[edges[a][c]]);
			if(y[edges[a][c]] != a) dfs(y[edges[a][c]]);
		}	
	}
}

struct node{
	node *l, *r;
	int le, re; // left edge, right edge (inclusive)
	int sum;
	node(){}
};
node * root[310000];

int add(int lx, int rx, node * a){
	if(a == NULL) return 0;
	if(lx == a->le && rx == a->re) return a->sum;
	if(rx <= a->l->re) return add(lx,rx,a->l);
	if(lx >= a->r->le ) return add(lx,rx,a->r);
	return add(lx,a->l->re,a->l) + add(a->r->le,rx,a->r);
}
node * build(int lx, int rx){
	node *a = new node();
	a->le = lx;
	a->re = rx;
	a->sum = 0;
	if(lx == rx){
		a->l = a->r = NULL;	
		return a;
	}
	a->l = build(lx,(lx+rx)/2);
	a->r = build((lx+rx)/2+1, rx);
	return a;
}

node* upd(int x, int val, node * a){
	if(a == NULL) return a;
	if(x < a->le || x > a->re) return a;
	node* newa = new node();
	newa->le = a->le;
	newa->re = a->re;
	newa->l = upd(x,val,a->l);
	newa->r = upd(x,val,a->r);
	if(newa->le == newa->re){
		newa->sum = val;
	} else {
		newa->sum = newa->l->sum + newa->r->sum;
	}
	return newa;
}
int main(){
	int n, m, q;
	scanf("%d%d%d", &n, &m, &q);
	for(int i = 1; i < n; i++) scanf("%d%d", &x[i], &y[i]);
	for(int i = 0; i < m; i++) scanf("%d", &d[i]);
	for(int i = 0; i < q; i++) scanf("%d", &c[i]);
	for(int i = 1; i < n; i++) t[i] = 0;
	for(int i = 0; i < m; i++){
		t[d[i]] = 1-t[d[i]];
	}
	for(int i = 1; i < n; i++){
		if(t[i]){
			d[m++] = i;
			t[i] = 1-t[i];
		}
	}
	// 1 2 1 4 4 3 2 3
	int ok = 1;
	for(int i = 1; i < n; i++) if((x[i] != i) || (y[i] != i+1)) ok = 0;
	if(q == 1 || !ok){
		for(int z = 0; z < q; z++){
			for(int i = 1; i <= n; i++) vis[i] = 0;
			vis[c[z]] = 1;
			for(int i = 1; i < n; i++){
				edges[x[i]].push_back(i);
				edges[y[i]].push_back(i);
			}
			for(int i = m-1; i >= 0; i--){
				t[d[i]] = 1-t[d[i]];
				if(t[d[i]] && (vis[x[d[i]]] ^ vis[y[d[i]]]) ){
					dfs(x[d[i]]);
					dfs(y[d[i]]);
				}
			}
			int ans = 0;
			for(int i = 1; i <= n; i++){
				ans += vis[i];
			}
			printf("%d\n", ans);
		}
		return 0;
	}

	for(int zz = 0; zz < 2; zz++){
		root[0] = build(0,n);
		for(int i = 1; i <= n; i++){
			ints[i].clear();
			inte[i].clear();
			ans[i].clear();
		}
		for(int i = 0; i < m; i++){
			root[i] = upd(d[i],1-t[d[i]],root[max(i-1,0)] );
			//for(int r = 1; r < n; r++) cout << add(r,r,root[i]) << " ";
			//cout << endl;
			t[d[i]] = 1-t[d[i]];
			if(t[d[i]]){
				ints[d[i]].push_back(i);
			} else {
				inte[d[i]].push_back(i-1);		
			}
		}
		//cout << endl;
		for(int i = 1; i < n; i++){
			for(int j = 0; j < ints[i].size(); j++){
				int s = 0;
				int e = i;
				while(s+1 < e){
					int m = (s+e)/2;
					if(add(m,i,root[inte[i][j]]) == i-m+1) e = m;
					else s = m;
				}
				int s1 = -1;
				int e1 = inte[s].size();
				while(s1 +1< e1){
					int m1 = (s1+e1)/2;
					if(inte[s][m1] < inte[i][j]) s1 = m1;
					else e1 = m1;				
				}

				if(s1 >= 0){
					ans[i].push_back(ans[s][s1]);
				} else {
					ans[i].push_back(s);
				}
			}
		}
		for(int i = 1; i < n; i++){
			int a2 = 0;
			for(int j = 0; j < ints[i].size(); j++){
				a2 = max(a2,i-ans[i][j]);
			}
			numreach[i+1] += a2;
			//cout << i+1 << " " << a2 << endl;
		}
		//cout << endl;
		reverse(numreach+1,numreach+n+1);
		for(int i = 0; i < m; i++){
			d[i] = n-d[i];
		}
	}
	for(int i = 0; i < q; i++){
		cout << numreach[c[i]]+1 << endl;
	}
}

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

synchronization.cpp: In function 'void dfs(int)':
synchronization.cpp:13:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int c = 0; c < edges[a].size(); c++){
                   ^
synchronization.cpp: In function 'int main()':
synchronization.cpp:128:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0; j < ints[i].size(); j++){
                     ^
synchronization.cpp:153:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0; j < ints[i].size(); j++){
                     ^
synchronization.cpp:67:29: 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:68:56: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i < n; i++) scanf("%d%d", &x[i], &y[i]);
                                                        ^
synchronization.cpp:69:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < m; i++) scanf("%d", &d[i]);
                                               ^
synchronization.cpp:70:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < q; i++) scanf("%d", &c[i]);
                                               ^

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