oj.uz

Submission #30569

# Submission time Handle Problem Language Result Execution time Memory
30569 2017-07-25T00:16:03 Z azneye Synchronization (JOI13_synchronization) C++14
30 / 100
 5543 ms 262144 KB 
#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;
	}
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 18976 KB Output is correct
2 Correct 0 ms 18976 KB Output is correct
3 Correct 0 ms 18976 KB Output is correct
4 Correct 0 ms 18976 KB Output is correct
5 Correct 6 ms 18976 KB Output is correct
6 Correct 6 ms 18976 KB Output is correct
7 Correct 9 ms 19372 KB Output is correct
8 Correct 13 ms 19372 KB Output is correct
9 Correct 6 ms 19372 KB Output is correct
10 Correct 99 ms 22276 KB Output is correct
11 Correct 109 ms 22276 KB Output is correct
12 Correct 73 ms 22144 KB Output is correct
13 Correct 83 ms 22692 KB Output is correct
14 Correct 96 ms 22276 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 24636 KB Output is correct
2 Correct 66 ms 23196 KB Output is correct
3 Correct 93 ms 26176 KB Output is correct
4 Correct 59 ms 23396 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 18976 KB Output is correct
2 Correct 3 ms 18976 KB Output is correct
3 Correct 0 ms 19240 KB Output is correct
4 Correct 9 ms 19240 KB Output is correct
5 Correct 0 ms 19108 KB Output is correct
6 Correct 16 ms 21880 KB Output is correct
7 Correct 186 ms 55276 KB Output is correct
8 Memory limit exceeded 1869 ms 262144 KB Memory limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 1489 ms 262144 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 18976 KB Output is correct
2 Correct 3 ms 18976 KB Output is correct
3 Correct 3 ms 18976 KB Output is correct
4 Correct 3 ms 19108 KB Output is correct
5 Correct 443 ms 28660 KB Output is correct
6 Memory limit exceeded 5543 ms 262144 KB Memory limit exceeded
7 Halted 0 ms 0 KB -