Submission #163204

#	Time	Username	Problem	Language	Result	Execution time	Memory
163204		TadijaSebez	스파이 (JOI13_spy)	C++11	100 / 100	476 ms	21376 KiB

spy

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=2050;
int sum[N][N];
void Add(int x, int y, int f)
{
	for(int i=x;i<N;i+=i&-i)
		for(int j=y;j<N;j+=j&-j)
			sum[i][j]+=f;
}
void Add(int x1, int x2, int y1, int y2)
{
	Add(x1,y1,1);
	Add(x2+1,y1,-1);
	Add(x1,y2+1,-1);
	Add(x2+1,y2+1,1);
}
int Get(int x, int y)
{
	int ans=0;
	for(int i=x;i;i-=i&-i)
		for(int j=y;j;j-=j&-j)
			ans+=sum[i][j];
	return ans;
}
struct Tree
{
	vector<int> E[N];
	int lid[N],rid[N],tid,root;
	Tree(){}
	void AddEdge(int u, int p)
	{
		if(p==0) root=u;
		else E[p].pb(u);
	}
	void DFS(int u){ lid[u]=++tid;for(int v:E[u]) DFS(v);rid[u]=tid;}
	void Euler(){ DFS(root);}
} JOI,IOI;
int main()
{
	int n,m,p,q;
	scanf("%i %i",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%i %i",&p,&q);
		JOI.AddEdge(i,p);
		IOI.AddEdge(i,q);
	}
	JOI.Euler();
	IOI.Euler();
	while(m--)
	{
		int e,s;
		scanf("%i %i",&e,&s);
		Add(JOI.lid[e],JOI.rid[e],IOI.lid[s],IOI.rid[s]);
	}
	for(int i=1;i<=n;i++) printf("%i\n",Get(JOI.lid[i],IOI.lid[i]));
	return 0;
}

Compilation message (stderr)

spy.cpp: In function 'int main()':
spy.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
spy.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&p,&q);
   ~~~~~^~~~~~~~~~~~~~~
spy.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&e,&s);
   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70