Submission #873456

#	Time	Username	Problem	Language	Result	Execution time	Memory
873456		AMnu	Synchronization (JOI13_synchronization)	C++14	100 / 100	191 ms	84168 KiB

synchronization

# 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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40