oj.uz

Submission #995358

# Submission time Handle Problem Language Result Execution time Memory
995358 2024-06-08T22:53:01 Z vjudge1 Synchronization (JOI13_synchronization) C++17
0 / 100
 184 ms 262144 KB 
#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repa(a,b) for(auto a:b)
#define ll long long
#define pb push_back
#define endl "\n"
#define pii pair<int, int>
#define fi first
#define se second
#define mid ((l+r)>>1)

using namespace std;

struct segtree{
	segtree *left, *right;
	int l, r, v=0;
	segtree(int x, int y): l(x), r(y){
		if(l==r) return;
		left = new segtree(l,mid);
		right= new segtree(mid+1,r);
	}
	void update(int x){
		if(r<x || x<l) return;
		if(x<=l && r<=x){
			v^=1;
			return;
		}
		left->update(x);
		right->update(x);
		v=((left->v)&(right->v));
	}
	int query(int x, int y){
		if(r<x || y<l) return 1;
		if(x<=l && r<=y) return v;
		return ((left->query(x,y))&(right->query(x,y)));
	}
};

const int lim=1e5+1000;
int sz[lim], tin[lim], root[lim], par[lim], hvy[lim], node[lim], timer;
vector<int> adj[lim];
bitset<lim> vnode[lim];
segtree ST(0,lim);

void sztree(int u, int p){
	sz[u]=1;
	hvy[u]=lim-1;
	par[u]=p;
	repa(v,adj[u]){
		if(v==p) continue;
		sztree(v,u);
		sz[u]+=sz[v];
		if(sz[hvy[u]]<sz[v]) hvy[u]=v;
	}
}

void dfs_hld(int u, int p){
	tin[u]=timer++;
	node[tin[u]]=u;
	repa(v,adj[u]){
		if(v!=hvy[u]) continue;
		root[v]=root[u];
		dfs_hld(v,u);
	}
	repa(v,adj[u]){
		if(v==hvy[u] || v==p) continue;
		root[v]=v;
		dfs_hld(v,u);
	}
}

int query(int u){
	while(ST.query(tin[root[u]],tin[u])) u=par[u];
	//PINCHE BINARIA COMO NO ME SALGA ME PEGO UN TIRO
	int l, r;
	l=tin[root[u]],r=tin[u];
	while(l<=r){
		if(ST.query(mid,r)) r=mid-1;
		else l=mid+1;
	}
	if(r<tin[u]) return node[r];
	else return u;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m, q, u, v;
	cin>>n>>m>>q;
	pii edges[n];
	rep(i,1,n+1) vnode[i].set(i);
	rep(i,1,n){
		cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
		edges[i]={u,v};
	}
	sztree(1,0);
	rep(i,1,n) if(par[edges[i].fi]!=edges[i].se) swap(edges[i].fi,edges[i].se);
	root[1]=1;
	dfs_hld(1,0);
	while(m--){
		cin>>u;
		u=edges[u].fi;
		v=query(u);
		if(v!=u) vnode[u]|=vnode[v];
		ST.update(tin[u]);
		v=query(u);
		if(v!=u) vnode[v]|=vnode[u];
	}
	while(q--){
		cin>>u;
		v=query(u);
		if(v!=u) vnode[u]|=vnode[v];
		cout<<vnode[u].count()<<endl;
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 13916 KB Output is correct
2 Correct 7 ms 13932 KB Output is correct
3 Correct 8 ms 14068 KB Output is correct
4 Correct 8 ms 14168 KB Output is correct
5 Correct 8 ms 16220 KB Output is correct
6 Correct 13 ms 26416 KB Output is correct
7 Correct 63 ms 139828 KB Output is correct
8 Correct 71 ms 139756 KB Output is correct
9 Correct 68 ms 139856 KB Output is correct
10 Runtime error 47 ms 262144 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14172 KB Output is correct
2 Correct 8 ms 14172 KB Output is correct
3 Correct 10 ms 16220 KB Output is correct
4 Correct 8 ms 16220 KB Output is correct
5 Correct 8 ms 16220 KB Output is correct
6 Correct 19 ms 26676 KB Output is correct
7 Correct 184 ms 140560 KB Output is correct
8 Runtime error 51 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13912 KB Output is correct
2 Correct 8 ms 14168 KB Output is correct
3 Correct 7 ms 14172 KB Output is correct
4 Correct 9 ms 16220 KB Output is correct
5 Correct 22 ms 26568 KB Output is correct
6 Correct 119 ms 139840 KB Output is correct
7 Runtime error 51 ms 262144 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -