Submission #686441

#	Time	Username	Problem	Language	Result	Execution time	Memory
686441		vjudge1	Regions (IOI09_regions)	C++14	0 / 100	28 ms	26092 KiB

regions

#include<stdio.h>
#include<vector>
#define N 200009
#define M 25000
#define B 999
using namespace std;
inline char nc()
{
	static char buf[99999],*l,*r;
	return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
	char c=nc();for(;c<'0'||'9'<c;c=nc());
	for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
inline void pc(const char&x)
{
	static char buf[99999],*r=buf;
	(!x||(*r++=x,r==buf+99999))&&(fwrite(buf,1,r-buf,stdout),r=buf);
}
inline void pr(const int&x){if(x>9)pr(x/10);pc(x%10+'0');}
int n,m,q,a[N],ans[N],dfn[N],sz[N],now,szsz[N],rem[N],tim[N];
vector<int>e[N],b[N],c[N],id[N];
inline int dfs(const int&i)
{
	dfn[i]=++now;sz[i]=1;
	++rem[a[i]];
	if(c[a[i]].size()<=B)for(int j=0;j<c[a[i]].size();++j)
		ans[id[a[i]][j]]+=rem[c[a[i]][j]];
	for(int j=0;j<e[i].size();++j)sz[i]+=dfs(e[i][j]);
	--rem[a[i]];
	return sz[i];
}
inline void upd(int i,const int&x){for(;i<=n;szsz[i]+=x,i+=i&-i);}
inline int qry(int i){int ans=0;for(;i;ans+=szsz[i],i&=i-1);return ans;}
main()
{
	read(n);read(m);read(q);read(a[0]);
	for(int i=1,f;i<n;++i)read(f),e[--f].emplace_back(i),read(a[i]);
	for(int i=0;i<n;++i)b[--a[i]].emplace_back(i);
	for(int i=0,u,v;i<q;++i)
	{
		read(u);read(v);--u;--v;
		c[v].emplace_back(u);id[v].emplace_back(i);
	}
	dfs(0);
	for(int i=0;i<m;tim[i++]=-1);
	for(int i=0;i<m;++i)if(c[i].size()>B)
	{
		for(int j=0;j<b[i].size();++j)upd(dfn[b[i][j]],1);
		for(int j=0;j<c[i].size();++j)
		{
			int&wr=rem[c[i][j]];
			if(tim[c[i][j]]^i)
			{
				wr=0;tim[c[i][j]]=i;
				for(int k:b[c[i][j]])wr+=qry(dfn[k]+sz[k]-1)-qry(dfn[k]-1);
			}
			ans[id[i][j]]=wr;
		}
		for(int j=0;j<b[i].size();++j)upd(dfn[b[i][j]],-1);
	}
	for(int i=0;i<q;pr(ans[i++]),pc('\n'));pc(0);
}

Compilation message (stderr)

regions.cpp: In function 'int dfs(const int&)':
regions.cpp:29:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  if(c[a[i]].size()<=B)for(int j=0;j<c[a[i]].size();++j)
      |                                   ~^~~~~~~~~~~~~~~
regions.cpp:31:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int j=0;j<e[i].size();++j)sz[i]+=dfs(e[i][j]);
      |              ~^~~~~~~~~~~~
regions.cpp: At global scope:
regions.cpp:37:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   37 | main()
      | ^~~~
regions.cpp: In function 'int main()':
regions.cpp:51:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for(int j=0;j<b[i].size();++j)upd(dfn[b[i][j]],1);
      |               ~^~~~~~~~~~~~
regions.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int j=0;j<c[i].size();++j)
      |               ~^~~~~~~~~~~~
regions.cpp:62:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for(int j=0;j<b[i].size();++j)upd(dfn[b[i][j]],-1);
      |               ~^~~~~~~~~~~~
regions.cpp:64:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   64 |  for(int i=0;i<q;pr(ans[i++]),pc('\n'));pc(0);
      |  ^~~
regions.cpp:64:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   64 |  for(int i=0;i<q;pr(ans[i++]),pc('\n'));pc(0);
      |                                         ^~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85