Submission #841369

#	Time	Username	Problem	Language	Result	Execution time	Memory
841369		parsadox2	Synchronization (JOI13_synchronization)	C++14	0 / 100	1782 ms	29276 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5 , M = 2e5 + 5;
int n , m , q , ans[N] , dis[N] , sz[N];
vector <pair<int ,int>> adj[N];
vector <int> query , ch[N] , all , vec;
bool dead[N];
pair <int , int> tim[N];

struct nod{
	int mx , lzy;
	nod()
	{
		mx = 0;
		lzy = 0;
	}
} tree[M << 2];

void pdfs(int v , int p = -1)
{
	sz[v] = 1;
	for(auto uu : adj[v])
	{
		int u = uu.second;
		if(u == p || dead[u])
			continue;
		pdfs(u , v);
		sz[v] += sz[u];
	}
}

int find_cent(int v , int val)
{
	for(auto uu : adj[v])
	{
		int u = uu.second;
		if(dead[u] || sz[u] > sz[v] || sz[u] <= val)
			continue;
		return find_cent(u , val);
	}
	return v;
}

void uplzy(int node , int lc , int rc)
{
	if(tree[node].lzy == 0)
		return;
	int tmp = tree[node].lzy;
	tree[lc].lzy += tmp;
	tree[rc].lzy += tmp;
	tree[lc].mx += tmp;
	tree[rc].mx += tmp;
	tree[node].lzy = 0;
}

int Get_first(int node = 1 , int nl = 0 , int nr = m)
{
	if(nr - nl == 1)
		return nl;
	int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
	if(tree[lc].mx >= tree[rc].mx)
		return Get_first(lc , nl , mid);
	else
		return Get_first(rc , mid , nr);
}

int Get_last(int node = 1 , int nl = 0 , int nr = m)
{
	if(nr - nl == 1)
		return nl;
	int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
	if(tree[rc].mx >= tree[lc].mx)
		return Get_last(rc , mid , nr);
	else
		return Get_last(lc , nl , mid);
}

void Add(int l , int r , int val , int node = 1 , int nl = 0 , int nr = m)
{
	if(r <= nl || nr <= l)
		return;
	if(l <= nl && nr <= r)
	{
		tree[node].mx += val;
		tree[node].lzy += val;
		return;
	}
	int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
	uplzy(node , lc , rc);
	Add(l , r , val , lc , nl , mid);   Add(l , r , val , rc , mid , nr);
	tree[node].mx = max(tree[lc].mx , tree[rc].mx);
}

void add(int ed , int ty = 1)
{
	for(int i = 0 ; i < ch[ed].size() ; i += 2)
		Add(ch[ed][i] , ch[ed][i + 1] , ty);
}

void dfs(int v , int p = -1)
{
	if(tree[1].mx < dis[v])
	{
		tim[v] = make_pair(-1 , -1);
		return;
	}
	tim[v] = make_pair(Get_first() , Get_last());
	for(auto uu : adj[v])
	{
		int u = uu.second , id = uu.first;
		if(dead[u] || u == p)
			continue;
		add(id);
		dfs(u , v);
		add(id , -1);
	}
}

void dfsp(int v , int p)
{
	if(tim[v] == make_pair(-1 , -1))
		return;
	vec.push_back(v);
	all.push_back(tim[v].first);
	for(auto uu : adj[v])
	{
		int u = uu.second;
		if(dead[u] || u == p) 
			continue;
		dfsp(u , v);
	}
}

void update(int v , int p , int ty = 1)
{
	all.clear();
	vec.clear();
	dfsp(v , p);
	sort(all.begin() , all.end());
	for(auto u : vec)
	{
		int pos = upper_bound(all.begin() , all.end() , tim[u].second) - all.begin();
		//cout << u << " " << tim[u].first << " " << tim[u].second << " " << ty * pos << endl;
		ans[u] += ty * (pos);
	}
}

void solve(int v)
{
	pdfs(v);
	int cent = find_cent(v , sz[v] / 2);
	if(q == 1 && !dead[query.back()])
		cent = query.back();
	dis[cent] = 0;
	dfs(cent);
	//cout << v << " " << cent << endl;
	update(cent , -1);
	for(auto uu : adj[cent])  if(!dead[uu.second])
		update(uu.second , cent , -1);
	dead[cent] = true;
	for(auto uu : adj[cent])  if(!dead[uu.second])
		solve(uu.second);
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);  cout.tie(0);
	cin >> n >> m >> q;
	for(int i = 1 ; i < n ; i++)
	{
		int u , v;  cin >> u >> v;
		adj[u].push_back({i , v});
		adj[v].push_back({i , u});
	}
	for(int i = 0 ; i < m ; i++)
	{
		int x;  cin >> x;
		ch[x].push_back(i);
	}
	for(int i = 0 ; i < q ; i++)
	{
		int v;  cin >> v;  query.push_back(v);
	}
	for(int i = 1 ; i < n ; i++)  if(ch[i].size() % 2 == 1)
		ch[i].push_back(m);
	solve(1);
	for(auto u : query)
		cout << ans[u] << '\n';
	return 0;
}

Compilation message (stderr)

synchronization.cpp: In function 'void add(int, int)':
synchronization.cpp:98:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |  for(int i = 0 ; i < ch[ed].size() ; i += 2)
      |                  ~~^~~~~~~~~~~~~~~

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