Submission #12637772


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
typedef int V;
// NV=3010101 -> 38MB
#define NV 6010101
#define def 0
struct PersistentSegmentTree { //[L,R)
    V comp(V a, V b) { return max(a,b); }




    // -- template ---------------------
    struct S { int l, r; V x; } v[NV];
    int cnt = 1, n = -1;
    void init(int _n) { n = _n; rep(i, 0, NV) v[i].l = v[i].r = 0, v[i].x = def; }
    void add(int &root, int l, int r, int i, int val) {
        v[cnt] = v[root]; root = cnt++;if (l + 1 == r) { v[root].x += val; return; }
        int mi = (l + r) / 2;if (i < mi) add(v[root].l, l, mi, i, val);
        else add(v[root].r, mi, r, i, val);
        v[root].x = comp(v[v[root].l].x, v[v[root].r].x);}
    void add(int &root, int i, int val) { assert(0 < n);add(root, 0, n, i, val); }
    void update(int &root, int l, int r, int i, int val) {v[cnt] = v[root];root = cnt++;
        if (l + 1 == r) {v[root].x = val;return;}int mi = (l + r) / 2;
        if (i < mi) update(v[root].l, l, mi, i, val);else update(v[root].r, mi, r, i, val);
        v[root].x = comp(v[v[root].l].x, v[v[root].r].x);}
    void update(int &root, int i, int val) {assert(0 < n);update(root, 0, n, i, val);}
    V allget(int root) { assert(0 < n); return v[root].x;}
    V get(int root, int l, int r, int L, int R) {
        if (l >= r) return def;if (l == L && r == R) return v[root].x;int mi = (L + R) / 2;
        V le = get(v[root].l, max(l, L), min(r, mi), L, mi);
        V ri = get(v[root].r, max(l, mi), min(r, R), mi, R);return comp(le, ri);}
    V get(int root, int l, int r) {assert(0 < n);return get(root, l, r, 0, n);}
};
vector<int> compress1(int* v, int n) {
    vector<int> dic;
    rep(i, 0, n) dic.push_back(v[i]);
    sort(all(dic));
    dic.erase(unique(all(dic)), dic.end());
    rep(i, 0, n) v[i] = lower_bound(all(dic), v[i]) - dic.begin();
    return dic;
}
/*---------------------------------------------------------------------------------------------------
            ∧_∧
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     @hamayanhamayan0
    /   \     | |
    /   / ̄ ̄ ̄ ̄/  |
  __(__ニつ/     _/ .| .|____
     \/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/














int N, a[201010];
vector<int> E[201010];
//---------------------------------------------------------------------------------------------------
PersistentSegmentTree pst;
int ans[201010];
void dfs(int cu = 0, int pa = -1, int root = 0) {
    int root2 = root;
    int ma = pst.get(root, 0, a[cu]);
    pst.update(root2, a[cu], max(pst.get(root, a[cu], a[cu] + 1), ma + 1));

    ans[cu] = pst.get(root2, 0, N);
    fore(to, E[cu]) if (to != pa) dfs(to, cu, root2);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> a[i];
    compress1(a, N);

    rep(i, 0, N - 1) {
        int u, v; cin >> u >> v;
        u--; v--;
        E[u].push_back(v);
        E[v].push_back(u);
    }

    pst.init(N);
    dfs();

    rep(i, 0, N) printf("%d\n", ans[i]);
}





Submission Info

Submission Time
Task F - LIS on Tree
User hamayanhamayan
Language C++ (GCC 9.2.1)
Score 600
Code Size 4028 Byte
Status AC
Exec Time 306 ms
Memory 124156 KB

Compile Error

./Main.cpp: In member function ‘V PersistentSegmentTree::get(int, int, int, int, int)’:
./Main.cpp:39:9: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   39 |         if (l >= r) return def;if (l == L && r == R) return v[root].x;int mi = (L + R) / 2;
      |         ^~
./Main.cpp:39:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
   39 |         if (l >= r) return def;if (l == L && r == R) return v[root].x;int mi = (L + R) / 2;
      |                                ^~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 1
AC × 17
Set Name Test Cases
Sample Sample_01.txt
All Sample_01.txt, caterpillar_01.txt, ni_01.txt, ni_02.txt, ni_03.txt, path_02.txt, path_04.txt, path_07.txt, path_08.txt, rand_01.txt, rand_02.txt, rand_03.txt, rand_04.txt, rand_05.txt, rand_large_01.txt, same_01.txt, star_01.txt
Case Name Status Exec Time Memory
Sample_01.txt AC 50 ms 78880 KB
caterpillar_01.txt AC 277 ms 96892 KB
ni_01.txt AC 54 ms 78796 KB
ni_02.txt AC 47 ms 78804 KB
ni_03.txt AC 49 ms 78816 KB
path_02.txt AC 287 ms 111708 KB
path_04.txt AC 269 ms 92468 KB
path_07.txt AC 271 ms 100088 KB
path_08.txt AC 279 ms 109440 KB
rand_01.txt AC 50 ms 78768 KB
rand_02.txt AC 48 ms 78796 KB
rand_03.txt AC 49 ms 78872 KB
rand_04.txt AC 48 ms 78820 KB
rand_05.txt AC 48 ms 78904 KB
rand_large_01.txt AC 306 ms 86820 KB
same_01.txt AC 272 ms 124156 KB
star_01.txt AC 288 ms 87304 KB