Submission #212692

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
212692	2020-03-24 06:23:48	PinkRabbit	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	723 ms	99064 KiB

constellation3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#include <algorithm>
#include <vector>
typedef long long LL;
const int MN = 200005, MM = 200005, MS = 4000005;
int N, A[MN], Root;
std::vector<int> G[MN];
void BuildCartesianTree() {
  static int stk[MN], tp, x;
  auto Add = [](int u, int v) {
    if (v) G[u].push_back(v);
  };
  for (int i = 1; i <= N; ++i) {
    for (x = 0; tp && A[stk[tp]] < A[i]; --tp)
      Add(stk[tp], x), x = stk[tp];
    Add(i, x), stk[++tp] = i;
  }
  for (x = 0; tp; --tp)
    Add(stk[tp], x), x = stk[tp];
  Root = x;
}
int dep[MN], par[MN][18];
void DFS(int u, int pa) {
  dep[u] = dep[par[u][0] = pa] + 1;
  for (int j = 0; 2 << j < dep[u]; ++j)
    par[u][j + 1] = par[par[u][j]][j];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

constellation3.cpp: In function 'int main()':
constellation3.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
constellation3.cpp:73:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
                               ~~~~~^~~~~~~~~~~~~
constellation3.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &M);
  ~~~~~^~~~~~~~~~
constellation3.cpp:80:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &x, &y, &w[i]), z = x;
   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65