oj.uz

Submission #202935

# Submission time Handle Problem Language Result Execution time Memory
202935 2020-02-18T18:16:21 Z arnold518 스파이 (JOI13_spy) C++14
100 / 100
 253 ms 20984 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1400 KB Output is correct
2 Correct 6 ms 1400 KB Output is correct
3 Correct 6 ms 1400 KB Output is correct
4 Correct 18 ms 1400 KB Output is correct
5 Correct 6 ms 1400 KB Output is correct
6 Correct 6 ms 1404 KB Output is correct
7 Correct 6 ms 1400 KB Output is correct
8 Correct 6 ms 1400 KB Output is correct
9 Correct 6 ms 376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16376 KB Output is correct
2 Correct 29 ms 16504 KB Output is correct
3 Correct 29 ms 16248 KB Output is correct
4 Correct 29 ms 16252 KB Output is correct
5 Correct 32 ms 16248 KB Output is correct
6 Correct 28 ms 16376 KB Output is correct
7 Correct 29 ms 16376 KB Output is correct
8 Correct 37 ms 16248 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 20728 KB Output is correct
2 Correct 139 ms 20728 KB Output is correct
3 Correct 213 ms 20600 KB Output is correct
4 Correct 178 ms 20984 KB Output is correct
5 Correct 206 ms 20728 KB Output is correct
6 Correct 140 ms 20216 KB Output is correct
7 Correct 253 ms 20712 KB Output is correct
8 Correct 232 ms 20732 KB Output is correct