oj.uz

Submission #873443

# Submission time Handle Problem Language Result Execution time Memory
873443 2023-11-15T06:00:30 Z AMnu Synchronization (JOI13_synchronization) C++17
50 / 100
 501 ms 262144 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 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);
	}
	
	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]);
			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)];
			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);
	}
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 1 ms 6648 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6588 KB Output is correct
6 Correct 3 ms 7260 KB Output is correct
7 Correct 26 ms 17744 KB Output is correct
8 Correct 22 ms 17136 KB Output is correct
9 Correct 26 ms 19652 KB Output is correct
10 Correct 478 ms 178428 KB Output is correct
11 Correct 435 ms 156864 KB Output is correct
12 Correct 294 ms 133452 KB Output is correct
13 Runtime error 501 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 150276 KB Output is correct
2 Correct 201 ms 150380 KB Output is correct
3 Correct 188 ms 131272 KB Output is correct
4 Correct 190 ms 131260 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 3 ms 7256 KB Output is correct
7 Correct 21 ms 16736 KB Output is correct
8 Correct 312 ms 131236 KB Output is correct
9 Correct 326 ms 131356 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 131460 KB Output is correct
2 Correct 206 ms 129268 KB Output is correct
3 Correct 209 ms 130096 KB Output is correct
4 Correct 213 ms 130240 KB Output is correct

Subtask #5
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 6488 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 30 ms 19312 KB Output is correct
7 Correct 498 ms 169860 KB Output is correct
8 Correct 326 ms 134260 KB Output is correct
9 Runtime error 469 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -