oj.uz

Submission #873456

# Submission time Handle Problem Language Result Execution time Memory
873456 2023-11-15T06:25:26 Z AMnu Synchronization (JOI13_synchronization) C++14
100 / 100
 191 ms 84168 KB 
# include <bits/stdc++.h>
# define fi first
# define se second
using namespace std;

struct segtree {
    segtree* L;
    segtree* R;
    int val;
    segtree(int x) {
        val = x;
        L = R = NULL;
    }
};

segtree* root;
segtree* info[100001];

segtree* upd(int lf, int rg, segtree* nw, int pos) {
    segtree* nl = new segtree(0);
    if(lf == rg) {
        nl->val = 1;
    } else {
        int mid = (lf + rg) / 2;
        if(pos <= mid) {
            if(nw->L == NULL) nw->L = new segtree(0);
            nl->R = nw->R;
            nl->L = upd(lf, mid, nw->L, pos);
        } else {
        	nl->L = nw->L;
            if(nw->R == NULL) nw->R = new segtree(0);
            nl->R = upd(mid+1, rg, nw->R, pos);
        }
        nl->val = 0;
        if(nl->L != NULL) nl->val += nl->L->val;
        if(nl->R != NULL) nl->val += nl->R->val;
    }
    return nl;
}

int N, M;

// optimize
segtree* merge(int lf, int rg, segtree* a, segtree* b) {
	if(a == NULL || !a->val) return b;
	if(b == NULL || !b->val) return a;
    if(a == b || lf == rg) return a;
	segtree* c = new segtree(0);
	int mid = (lf + rg) / 2;
	c->L = merge(lf, mid, a->L, b->L);
	c->R = merge(mid+1, rg, a->R, b->R);
	if(c->L != NULL) c->val += c->L->val;
	if(c->R != NULL) c->val += c->R->val;
	return c;
}

int ansa[100001], ansc[100001];
int Q, dpt[100001], sz[100001], mx[100001], bg[100001], pos[100001], par[100001], in[100001], rt[100001], t;
vector< pair<int, int> > sp;
vector<int> edge[100001];
bool tr[100001];

void dfs(int a, int pr, int dt) {
	par[a] = pr;
	dpt[a] = dt;
	sz[a] = 1;
	mx[a] = -1;
	bg[a] = -1;
	for(int i=0;i<edge[a].size();i++) {
		if(edge[a][i] == pr) continue;
		dfs(edge[a][i], a, dt+1);
		sz[a] += sz[edge[a][i]];
		if(mx[a] < sz[edge[a][i]]) {
			mx[a] = sz[edge[a][i]];
			bg[a] = edge[a][i];
		}
	}
}

void build_hld(int a, int pr, int root) {
	rt[a] = root;
	pos[t] = a;
	in[a] = t++;
	// rt[a] = root; // duplicate
	if(bg[a] != -1) build_hld(bg[a], a, root);
	for(int i=0;i<edge[a].size();i++) {
		if(edge[a][i] == pr || edge[a][i] == bg[a]) continue;
        // if(edge[a][i] == bg[a]) continue; // duplicate
		build_hld(edge[a][i], a, edge[a][i]); // root = ch
	}
}

int fen[100001];

void add(int a, int x) {
	while(a <= 1e5) {
		fen[a] += x;
		a += a&(-a);
	}
}

int qry(int a) {
	int as = 0;
	while(a > 0) {
		as += fen[a];
		a -= a&(-a);
	}
	return as;
}

int binser(int a) {
	int id = 0, sum = 0;
	for(int i=20;i>=0;i--) {
		id += (1 << i);
		if(id <= 1e5 && sum + fen[id] <= a) {
			sum += fen[id];
		} else {
			id -= (1 << i);
		}
	}
	return id;
}

int find(int a) {
	while(true) {
		int L = qry(1e5 - in[a] - 1);
		L = binser(L);
	//	cout<<"L : "<<L<<endl;
	//	if(a != 0) cout<<a<<" "<<L<<" "<<rt[a]<<endl;
		if(L >= 1e5 - in[rt[a]]) a = par[rt[a]];
		else {
			L++;
			return pos[(int) 1e5 - L];
		}
	}
}

int main() {
	scanf("%d %d %d", &N, &M, &Q);
	for(int i=1;i<N;i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		edge[a].push_back(b);
		edge[b].push_back(a);
		sp.push_back(make_pair(a, b));
	}
	
	dfs(1, 0, 0);
	build_hld(1, 0, 1);
	root = new segtree(0);
	for(int i=1;i<=N;i++) {
		add(1e5 - in[i], 1);
		info[i] = upd(1, N, root, i);
        ansa[i] = 1;
	}
	
	for(int i=0;i<M;i++) {
		int L;
		scanf("%d", &L);
		L--;
		if(dpt[sp[L].fi] < dpt[sp[L].se]) swap(sp[L].fi, sp[L].se);
		
		if(!tr[L]) {
			// sambungin L
			tr[L] = 1;
		//	cout<<"sp : "<<sp[L].se<<" "<<find(sp[L].se)<<endl;
			int KL = find(sp[L].se);
			// info[KL] = merge(1, N, info[sp[L].fi], info[KL]);
			ansa[KL] += ansa[sp[L].fi] - ansc[sp[L].fi];
            add(1e5 - in[sp[L].fi], -1);
		} else {
			// dipisah
			tr[L] = 0;
		//	cout<<"sp : "<<sp[L].se<<" "<<find(sp[L].se)<<" "<<sp[L].fi<<" "<<info[find(sp[L].se)].count()<<endl;
			// info[sp[L].fi] = info[find(sp[L].se)];
            ansa[sp[L].fi] = ansc[sp[L].fi] = ansa[find(sp[L].se)];
			add(1e5 - in[sp[L].fi], 1);
		}
	//	for(int i=1;i<=N;i++) cout<<info[find(i)].count()<<" ";
	//	cout<<endl;
	}
	while(Q--) {
		int v;
		scanf("%d", &v);
		// printf("%d\n", info[find(v)]->val);
        printf("%d\n", ansa[find(v)]);
	}
}

Compilation message

synchronization.cpp: In function 'void dfs(int, int, int)':
synchronization.cpp:69:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(int i=0;i<edge[a].size();i++) {
      |              ~^~~~~~~~~~~~~~~
synchronization.cpp: In function 'void build_hld(int, int, int)':
synchronization.cpp:86:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for(int i=0;i<edge[a].size();i++) {
      |              ~^~~~~~~~~~~~~~~
synchronization.cpp: In function 'int main()':
synchronization.cpp:139:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |  scanf("%d %d %d", &N, &M, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:142:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~
synchronization.cpp:159:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |   scanf("%d", &L);
      |   ~~~~~^~~~~~~~~~
synchronization.cpp:184:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |   scanf("%d", &v);
      |   ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 13 ms 12124 KB Output is correct
8 Correct 13 ms 12212 KB Output is correct
9 Correct 13 ms 12036 KB Output is correct
10 Correct 160 ms 73644 KB Output is correct
11 Correct 150 ms 73412 KB Output is correct
12 Correct 136 ms 81348 KB Output is correct
13 Correct 125 ms 75952 KB Output is correct
14 Correct 126 ms 75336 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 77500 KB Output is correct
2 Correct 112 ms 76444 KB Output is correct
3 Correct 112 ms 81312 KB Output is correct
4 Correct 119 ms 81240 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 15 ms 13044 KB Output is correct
8 Correct 160 ms 81348 KB Output is correct
9 Correct 159 ms 81348 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 81348 KB Output is correct
2 Correct 132 ms 81284 KB Output is correct
3 Correct 139 ms 81860 KB Output is correct
4 Correct 135 ms 81860 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 7004 KB Output is correct
6 Correct 18 ms 12124 KB Output is correct
7 Correct 191 ms 73908 KB Output is correct
8 Correct 161 ms 81404 KB Output is correct
9 Correct 143 ms 76864 KB Output is correct
10 Correct 181 ms 76744 KB Output is correct
11 Correct 139 ms 80676 KB Output is correct
12 Correct 138 ms 80728 KB Output is correct
13 Correct 134 ms 84168 KB Output is correct