Submission #202935

#	Time	Username	Problem	Language	Result	Execution time	Memory
202935		arnold518	스파이 (JOI13_spy)	C++14	100 / 100	253 ms	20984 KiB

spy

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2000;
const int MAXM = 5e5;

int N, M, A[MAXN+10][MAXN+10];

struct Tree
{
	vector<int> adj[MAXN+10];
	int in[MAXN+10], out[MAXN+10], cnt=0, root;

	void dfs(int now)
	{
		in[now]=++cnt;
		for(int nxt : adj[now]) dfs(nxt);
		out[now]=cnt;
	}
}TA, TB;

int main()
{
	int i, j;

	scanf("%d%d", &N, &M);
	for(i=1; i<=N; i++)
	{
		int pa, pb;
		scanf("%d%d", &pa, &pb);

		if(pa==0) TA.root=i;
		else TA.adj[pa].push_back(i);

		if(pb==0) TB.root=i;
		else TB.adj[pb].push_back(i);
	}

	TA.dfs(TA.root);
	TB.dfs(TB.root);

	for(i=1; i<=M; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		A[TA.in[a]][TB.in[b]]++;
		A[TA.in[a]][TB.out[b]+1]--;
		A[TA.out[a]+1][TB.in[b]]--;
		A[TA.out[a]+1][TB.out[b]+1]++;
	}

	for(i=1; i<=N; i++) for(j=1; j<=N; j++) A[i][j]+=A[i-1][j]+A[i][j-1]-A[i-1][j-1];

	for(i=1; i<=N; i++) printf("%d\n", A[TA.in[i]][TB.in[i]]);
}

Compilation message (stderr)

spy.cpp: In function 'int main()':
spy.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
spy.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &pa, &pb);
   ~~~~~^~~~~~~~~~~~~~~~~~
spy.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

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