Submission #68317

#	Time	Username	Problem	Language	Result	Execution time	Memory
68317		top34051	Synchronization (JOI13_synchronization)	C++17	100 / 100	1802 ms	96772 KiB

synchronization

#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 1e5 + 5;

int n,m,q;
vector<pii> way[maxn];
pii e[maxn];

int h[maxn], cur, st[maxn], ft[maxn];
set<pii> seg[maxn*4];
int  open[maxn];

int res[maxn], wow[maxn];

void dfs(int u, int last) {
	h[u] = h[last] + 1;
	st[u] = ++cur;
	for(auto tmp : way[u]) {
		int v = tmp.X, id = tmp.Y;
		if(v==last) continue;
		e[id] = {u,v};
		dfs(v,u);
	}
	ft[u] = cur;
}

void update_add(int pos, int l, int r, int x, int y, int u) {
	if(l>r || r<x || y<l) return ;
	if(x<=l && r<=y) {
		seg[pos].insert({-h[u],u});
		return ;
	}
	int mid = (l+r)/2;
	update_add(pos<<1,l,mid,x,y,u);
	update_add(pos<<1|1,mid+1,r,x,y,u);
}

void update_del(int pos, int l, int r, int x, int y, int u) {
	if(l>r || r<x || y<l) return ;
	if(x<=l && r<=y) {
		seg[pos].erase({-h[u],u});
		return ;
	}
	int mid = (l+r)/2;
	update_del(pos<<1,l,mid,x,y,u);
	update_del(pos<<1|1,mid+1,r,x,y,u);
}

pii query(int pos, int l, int r, int x) {
	if(l>r || r<x || x<l) return {0,0};
	pii tmp = {0,0};
	if(seg[pos].size()!=0) tmp = *seg[pos].begin();
	if(l==r) return tmp;
	int mid = (l+r)/2;
	return min(tmp, min(query(pos<<1,l,mid,x), query(pos<<1|1,mid+1,r,x)));
}

int main() {
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<n;i++) {
		int u,v; scanf("%d%d",&u,&v);
		way[u].push_back({v,i});
		way[v].push_back({u,i});
	}

	dfs(1,0);
	for(int u=1;u<=n;u++) {
        update_add(1,1,n,st[u],ft[u],u);
        res[u] = 1;
    }

	for(int i=1;i<=m;i++) {
		int x; scanf("%d",&x);
		int u = e[x].X, v = e[x].Y;
		if(!open[x]) {
			int root = query(1,1,n,st[u]).Y;
//			printf("root = %d  %d + %d - %d\n",root,res[root],res[v],wow[v]);
			res[root] = res[root] + res[v] - wow[v];
			res[v] = 0;
			wow[v] = 0;
			update_del(1,1,n,st[v],ft[v],v);
			open[x] = 1;
		}
		else {
			int root = query(1,1,n,st[u]).Y;
			res[v] = res[root];
			wow[v] = res[root];
//            printf("root = %d  %d  %d  %d\n",root,res[root],res[v],wow[v]);
			update_add(1,1,n,st[v],ft[v],v);
			open[x] = 0;
        }
	}

	while(q--) {
		int u; scanf("%d",&u);
		int root = query(1,1,n,st[u]).Y;
		printf("%d\n",res[root]);
	}
}

Compilation message (stderr)

synchronization.cpp: In function 'int main()':
synchronization.cpp:63:7: 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:65:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u,v; scanf("%d%d",&u,&v);
            ~~~~~^~~~~~~~~~~~~~
synchronization.cpp:77:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d",&x);
          ~~~~~^~~~~~~~~
synchronization.cpp:99:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u; scanf("%d",&u);
          ~~~~~^~~~~~~~~

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