Submission #239239

#	Time	Username	Problem	Language	Result	Execution time	Memory
239239		frodakcin	Synchronization (JOI13_synchronization)	C++11	100 / 100	333 ms	23544 KiB

synchronization

#include <cstdio>
#include <cstring>
#include <cassert>
#include <functional>
#include <vector>
#include <set>

const int MN = 1e5+10, MM = 2e5+10;
struct edge
{
public:
	int n, id;
};
std::vector<edge> a[MN];
int N, M, Q, p[MN][1], s[MN], d[MN], h[MN], t[MN], l[MN], f[MN], m[MN], w[MN];
const auto cmp=[](int x, int y){return d[x]>d[y];};//decreasing level/depth. no collisions should occur because these are on heavy chains
typedef std::set<int, decltype(cmp)> Set;
Set *hv[MN];
bool u[MN];

void dfs(int n=1)
{
	s[n]=1;
	for(auto x:a[n])
		if(x.n!=p[n][0])
			m[x.id]=x.n, p[x.n][0]=n, d[x.n]=d[n]+1, dfs(x.n), s[n]+=s[x.n];
}
void dfs2(int n=1)
{
	for(auto x:a[n])
		if(x.n!=p[n][0])
		{
			if(s[x.n]*2>s[n])//>= is ok too
			{
				h[n]=x.n;
				if(!~t[n])
					t[n]=n, l[n]=0, hv[n]=new Set(cmp);
				t[x.n]=t[n], l[x.n]=l[n]+1;
			}
			dfs2(x.n);
		}
	if(~t[n])
		hv[t[n]]->insert(n);
}
int get(int n)
{
	for(;;)
		if(~t[n])
		{
			Set *set = hv[t[n]];
			auto it=set->lower_bound(n);
			if(it == set->end())
				n=p[t[n]][0];
			else
				return *it;
		}
		else if(u[n])
			n=p[n][0];
		else
			return n;
}
int main(void)
{
	scanf("%d%d%d", &N, &M, &Q);
	for(int i=1,x,y;i<N;++i)
		scanf("%d%d", &x, &y), a[x].push_back({y, i}), a[y].push_back({x, i});
	memset(t, -1, sizeof t);
	memset(h, -1, sizeof h);
	dfs();
	dfs2();
	for(int i=1;i<=N;++i) f[i]=1;
	for(int i=0,k;i<M;++i)
	{
		scanf("%d", &k);
		k = m[k];//child of affected edge
		if(u[k])
		{
			int c=f[get(k)];
			w[k]=f[k]=c;
			if(~t[k])
				hv[t[k]]->insert(k);
		}
		else
		{
			//assert(get(k) == k);
			f[get(p[k][0])]+=f[k]-w[k];//f[k] and w[k] can be set to nan
			if(~t[k])
				hv[t[k]]->erase(k);
		}
		u[k]^=1;
	}
	for(int i=0,k;i<Q;++i)
		scanf("%d", &k), printf("%d\n", f[get(k)]);
	for(int i=1;i<=N;++i)
		if(t[i]==i)
			delete hv[i];
	return 0;
}

Compilation message (stderr)

synchronization.cpp: In function 'int main()':
synchronization.cpp:64: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:66:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y), a[x].push_back({y, i}), a[y].push_back({x, i});
   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &k);
   ~~~~~^~~~~~~~~~
synchronization.cpp:93:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &k), printf("%d\n", f[get(k)]);
   ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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