Submission #212898

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
212898	2020-03-24 13:03:27	sinatori	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	1066 ms	96100 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 <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(V) V.begin(),V.end()
ll W[400010], A[200010], seg[524288], rt[524288], as[1048576], lc[1048576], par[400010], hlnum[400010], hlseg[400010], hltop[400010], hlpar[400010];
vector<pair<int, int>> H;
vector<int> T[400010];
tuple<int, int, int> R[400010];
//hlnumはhl分解後の「セグ木上での番号」、hlsegはhl分解後のセグ木のx番目の「頂点番号」、hltopはその頂点が属する鎖の一番根に近いやつの「頂点番号」、hlparは鎖の繋がっている親ノードの「頂点番号」
int wgh(int x) {
  int a = 1;
  for (int j : T[x])a += wgh(j);
  W[x] = a;
  return a;
}
void hld(int x, int me, int& num) {
  int mw = 0, ms = 0;
  hlnum[x] = num;
  hlseg[num] = x;
  hltop[x] = me;
  hlpar[x] = hlpar[me];
  if (T[x].size() == 0)return;
  for (int i : T[x]) {
    if (W[i] > mw)ms = i, mw = W[i];
  }
  num++;
  hld(ms, me, num);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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