oj.uz

답안 #163204

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
163204 2019-11-11T18:07:09 Z TadijaSebez 스파이 (JOI13_spy) C++11
100 / 100
 476 ms 21376 KB 
#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

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1912 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 4 ms 1912 KB Output is correct
4 Correct 3 ms 1656 KB Output is correct
5 Correct 4 ms 2040 KB Output is correct
6 Correct 3 ms 764 KB Output is correct
7 Correct 4 ms 1912 KB Output is correct
8 Correct 4 ms 2040 KB Output is correct
9 Correct 2 ms 632 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 13176 KB Output is correct
2 Correct 9 ms 888 KB Output is correct
3 Correct 15 ms 12920 KB Output is correct
4 Correct 14 ms 10872 KB Output is correct
5 Correct 16 ms 13816 KB Output is correct
6 Correct 10 ms 1400 KB Output is correct
7 Correct 17 ms 13432 KB Output is correct
8 Correct 16 ms 14328 KB Output is correct

Subtask #3
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 360 ms 21368 KB Output is correct
2 Correct 387 ms 5256 KB Output is correct
3 Correct 394 ms 20984 KB Output is correct
4 Correct 424 ms 21376 KB Output is correct
5 Correct 426 ms 20856 KB Output is correct
6 Correct 344 ms 6976 KB Output is correct
7 Correct 472 ms 21112 KB Output is correct
8 Correct 476 ms 21128 KB Output is correct