oj.uz

Submission #1037713

# Submission time Handle Problem Language Result Execution time Memory
1037713 2024-07-29T07:16:28 Z 정민찬(#10982) Tourism (JOI23_tourism) C++17
34 / 100
 5000 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

const int inf = 2e9;

int N, M, Q;
vector<int> adj[100010];
int C[100010];
vector<int> s[100010];
int L[100010];
int R[100010];
int ans[100010];

int chk[100010];
int sz[100010];

int getSize(int x, int p) {
    sz[x] = 1;
    for (auto &y : adj[x]) {
        if (y == p || chk[y]) continue;
        sz[x] += getSize(y, x);
    }
    return sz[x];
}

int getCent(int x, int p, int cap) {
    for (auto &y : adj[x]) {
        if (y == p || chk[y]) continue;
        if (sz[y] * 2 > cap) return getCent(y, x, cap);
    }
    return x;
}

struct Fenwick{
    vector<int> tree;
    void init(int n) {
        tree.assign(n+1, 0);
    }
    void upd(int i, int v, int n) {
        while (i <= n) {
            tree[i] += v;
            i += i & -i;
        }
    }
    int qry(int i) {
        int ret = 0;
        while (i) {
            ret += tree[i];
            i -= i & -i;
        }
        return ret;
    }
    int qry(int l, int r) {
        return qry(r) - qry(l-1);
    }
};

struct MaxSegmentTree{
    vector<int> tree;
    void init(int n) {
        int sz = 1 << __lg(n-1) + 2;
        tree.assign(sz, -inf);
    }
    void update(int node, int s, int e, int tar, int val) {
        if (s > tar || tar > e) return;
        if (s == e) {
            tree[node] = val;
            return;
        }
        int mid = s + e >> 1;
        update(node*2, s, mid, tar, val);
        update(node*2+1, mid+1, e, tar, val);
        tree[node] = max(tree[node*2], tree[node*2+1]);
    }
    int query(int node, int s, int e, int l, int r) {
        if (l > e || s > r) return -inf;
        if (l <= s && e <= r) return tree[node];
        int mid = s + e >> 1;
        return max(query(node*2, s, mid, l, r), query(node*2+1, mid+1, e, l, r));
    }
};

Fenwick seg;
MaxSegmentTree mxs, mns;

vector<int> D;

int Idx(int v) {
    return lower_bound(D.begin(), D.end(), v) - D.begin() + 1;
}

void dfs(int x, int p) {
    for (auto &k : s[x]) {
        D.push_back(k);
    }
    for (auto &y : adj[x]) {
        if (y == p || chk[y]) continue;
        dfs(y, x);
    }
}

void dfs2(int x, int p, int r) {
    for (auto &k : s[x]) {
        int idx = Idx(k);
        mxs.update(1, 1, D.size(), idx, r);
        mns.update(1, 1, D.size(), idx, -r);
    }
    for (auto &y : adj[x]) {
        if (y == p || chk[y]) continue;
        dfs2(y, x, r);
    }
}

int getSize2(int x, int p) {
    sz[x] = s[x].size();
    for (auto &y : adj[x]) {
        if (y == p || chk[y]) continue;
        sz[x] += getSize2(y, x);
    }
    return sz[x];
}

set<int> ss[100010];
int id[100010];
int pv;
vector<pair<int,int>> save[100010];

void my_ins(int i, int k, int cnt, int x) {
    /*auto rit = ss[i].lower_bound(k);
    if (rit != ss[i].end()) {
        save[k+1].push_back({*rit, cnt});
    }
    if (rit != ss[i].begin()) {
        auto lit = prev(rit);
        save[*lit+1].push_back({k, cnt});
        if (rit != ss[i].end()) {
            save[*lit+1].push_back({*rit, -cnt});
        }
    }*/
    ss[i].insert(k);
}

int dfs4(int x, int p, int cnt) {
    int mxsz = -1, ch = -1;
    for (auto &y : adj[x]) {
        if (y == p || chk[y]) continue;
        if (sz[y] > mxsz) {
            mxsz = sz[y];
            ch = y;
        }
    }
    if (ch == -1) {
        id[x] = pv ++;
        int p = 0;
        ss[id[x]].insert(0);
        for (auto &k : s[x]) {
            ss[id[x]].insert(Idx(k));
            save[p+1].push_back({Idx(k), 1});
            p = Idx(k);
        }
        return id[x];
    }
    else {
        id[x] = dfs4(ch, x, cnt + 1);
        for (auto &y : adj[x]) {
            if (y == p || y == ch || chk[y]) continue;
            int z = dfs4(y, x, 1);
            for (auto &k : ss[z]) {
                if (k == 0) continue;
                my_ins(id[x], k, cnt, x);
            }
        }
        for (auto &k : s[x]) {
            my_ins(id[x], Idx(k), cnt, x);
        }
        int p = 0;
        for (auto &k : ss[id[x]]) {
            if (k == 0) continue;
            save[p+1].push_back({k, 1});
            p = k;
        }
        return id[x];
    }
}

void dnc(int x, vector<int> qrs) {
    if (qrs.empty()) return;
    x = getCent(x, -1, getSize(x, -1));
    D.clear();
    dfs(x, -1);
    sort(D.begin(), D.end());
    mxs.init(D.size()); mns.init(D.size());
    for (int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];
        if (chk[y]) continue;
        dfs2(y, x, i);
    }
    for (auto &k : s[x]) {
        int idx = Idx(k);
        mxs.update(1, 1, D.size(), idx, -1);
        mns.update(1, 1, D.size(), idx, 1);
    }
    vector<int> curq;
    vector<int> nxtq[adj[x].size()];
    for (auto &i : qrs) {
        int li = Idx(L[i]), ri = Idx(R[i]);
        int ret1 = mxs.query(1, 1, D.size(), li, ri);
        int ret2 = -mns.query(1, 1, D.size(), li, ri);
        if (ret1 == ret2 && ret1 != -1) {
            nxtq[ret1].push_back(i);
        }
        else {
            curq.push_back(i);
        }
    }
    getSize2(x, -1);
    pv = 0;
    dfs4(x, -1, 0);
    for (int i=0; i<pv; i++) {
        ss[i].clear();
    }
    seg.init(D.size());
    sort(curq.begin(), curq.end(), [&] (int &u, int &v) { return L[u] < L[v]; });
    int j = 0;
    for (int i=1; i<=D.size(); i++) {
        for (auto &[pos, v] : save[i]) {
            seg.upd(pos, v, D.size());
        }
        while (j < curq.size() && L[curq[j]] == D[i-1]) {
            ans[curq[j]] = seg.qry(Idx(L[curq[j]]), Idx(R[curq[j]]));
            j ++;
        }
    }
    for (int i=0; i<=D.size() + 2; i++) {
        save[i].clear();
    }
    chk[x] = 1;
    for (int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];
        if (chk[y]) continue;
        dnc(y, nxtq[i]);
    }
}

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> M >> Q;
    for (int i=0; i<N-1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i=1; i<=M; i++) {
        cin >> C[i];
        s[C[i]].push_back(i);
    }
    for (int i=1; i<=Q; i++) {
        cin >> L[i] >> R[i];
    }
    for (int i=1; i<=N; i++) {
        sort(s[i].begin(), s[i].end());
    }
    vector<int> initq(Q);
    iota(initq.begin(), initq.end(), 1);
    dnc(1, initq);
    for (int i=1; i<=Q; i++) {
        cout << ans[i] << '\n';
    }
}

Compilation message

tourism.cpp: In member function 'void MaxSegmentTree::init(int)':
tourism.cpp:65:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   65 |         int sz = 1 << __lg(n-1) + 2;
      |                       ~~~~~~~~~~^~~
tourism.cpp: In member function 'void MaxSegmentTree::update(int, int, int, int, int)':
tourism.cpp:74:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         int mid = s + e >> 1;
      |                   ~~^~~
tourism.cpp: In member function 'int MaxSegmentTree::query(int, int, int, int, int)':
tourism.cpp:82:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |         int mid = s + e >> 1;
      |                   ~~^~~
tourism.cpp: In function 'void dnc(int, std::vector<int>)':
tourism.cpp:197:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |     for (int i=0; i<adj[x].size(); i++) {
      |                   ~^~~~~~~~~~~~~~
tourism.cpp:229:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  229 |     for (int i=1; i<=D.size(); i++) {
      |                   ~^~~~~~~~~~
tourism.cpp:233:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  233 |         while (j < curq.size() && L[curq[j]] == D[i-1]) {
      |                ~~^~~~~~~~~~~~~
tourism.cpp:238:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  238 |     for (int i=0; i<=D.size() + 2; i++) {
      |                   ~^~~~~~~~~~~~~~
tourism.cpp:242:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  242 |     for (int i=0; i<adj[x].size(); i++) {
      |                   ~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14696 KB Output is correct
4 Correct 3 ms 14936 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 3 ms 14940 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 3 ms 14940 KB Output is correct
14 Correct 3 ms 14940 KB Output is correct
15 Correct 4 ms 15196 KB Output is correct
16 Correct 4 ms 15196 KB Output is correct
17 Correct 4 ms 15196 KB Output is correct
18 Correct 4 ms 14940 KB Output is correct
19 Correct 4 ms 14940 KB Output is correct
20 Correct 4 ms 15196 KB Output is correct
21 Correct 3 ms 14940 KB Output is correct
22 Correct 4 ms 14940 KB Output is correct
23 Correct 4 ms 14936 KB Output is correct
24 Correct 3 ms 14940 KB Output is correct
25 Correct 3 ms 14988 KB Output is correct
26 Correct 3 ms 14940 KB Output is correct
27 Correct 3 ms 14940 KB Output is correct
28 Correct 3 ms 14940 KB Output is correct
29 Correct 4 ms 14904 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14696 KB Output is correct
4 Correct 3 ms 14936 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 3 ms 14940 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 3 ms 14940 KB Output is correct
14 Correct 3 ms 14940 KB Output is correct
15 Correct 4 ms 15196 KB Output is correct
16 Correct 4 ms 15196 KB Output is correct
17 Correct 4 ms 15196 KB Output is correct
18 Correct 4 ms 14940 KB Output is correct
19 Correct 4 ms 14940 KB Output is correct
20 Correct 4 ms 15196 KB Output is correct
21 Correct 3 ms 14940 KB Output is correct
22 Correct 4 ms 14940 KB Output is correct
23 Correct 4 ms 14936 KB Output is correct
24 Correct 3 ms 14940 KB Output is correct
25 Correct 3 ms 14988 KB Output is correct
26 Correct 3 ms 14940 KB Output is correct
27 Correct 3 ms 14940 KB Output is correct
28 Correct 3 ms 14940 KB Output is correct
29 Correct 4 ms 14904 KB Output is correct
30 Correct 7 ms 15704 KB Output is correct
31 Correct 7 ms 15340 KB Output is correct
32 Correct 8 ms 15708 KB Output is correct
33 Correct 8 ms 15452 KB Output is correct
34 Correct 9 ms 15452 KB Output is correct
35 Correct 7 ms 15452 KB Output is correct
36 Correct 7 ms 15596 KB Output is correct
37 Correct 7 ms 15708 KB Output is correct
38 Correct 36 ms 26332 KB Output is correct
39 Correct 37 ms 26452 KB Output is correct
40 Correct 35 ms 26716 KB Output is correct
41 Correct 24 ms 25980 KB Output is correct
42 Correct 25 ms 25688 KB Output is correct
43 Correct 25 ms 25948 KB Output is correct
44 Correct 18 ms 19992 KB Output is correct
45 Correct 18 ms 19548 KB Output is correct
46 Correct 26 ms 20316 KB Output is correct
47 Correct 12 ms 19036 KB Output is correct
48 Correct 11 ms 18268 KB Output is correct
49 Correct 14 ms 20060 KB Output is correct
50 Correct 6 ms 15452 KB Output is correct
51 Correct 6 ms 15452 KB Output is correct
52 Correct 7 ms 15452 KB Output is correct
53 Correct 6 ms 15452 KB Output is correct
54 Correct 6 ms 15508 KB Output is correct
55 Correct 6 ms 15452 KB Output is correct
56 Correct 5 ms 14940 KB Output is correct
57 Correct 3 ms 14940 KB Output is correct
58 Correct 13 ms 15448 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 5 ms 14940 KB Output is correct
4 Runtime error 3073 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 136 ms 39912 KB Output is correct
3 Correct 221 ms 55240 KB Output is correct
4 Correct 171 ms 46784 KB Output is correct
5 Correct 305 ms 62668 KB Output is correct
6 Correct 296 ms 63172 KB Output is correct
7 Correct 284 ms 62676 KB Output is correct
8 Correct 287 ms 61636 KB Output is correct
9 Correct 304 ms 63428 KB Output is correct
10 Correct 294 ms 63176 KB Output is correct
11 Correct 311 ms 61648 KB Output is correct
12 Correct 291 ms 63680 KB Output is correct
13 Correct 457 ms 62412 KB Output is correct
14 Correct 891 ms 62476 KB Output is correct
15 Correct 1116 ms 64224 KB Output is correct
16 Correct 770 ms 63440 KB Output is correct
17 Correct 772 ms 63696 KB Output is correct
18 Correct 749 ms 62668 KB Output is correct
19 Correct 1560 ms 609004 KB Output is correct
20 Correct 1768 ms 704968 KB Output is correct
21 Correct 1491 ms 587460 KB Output is correct
22 Correct 1432 ms 560068 KB Output is correct
23 Correct 1744 ms 656576 KB Output is correct
24 Correct 1776 ms 665536 KB Output is correct
25 Correct 1724 ms 687084 KB Output is correct
26 Correct 1682 ms 643548 KB Output is correct
27 Correct 1668 ms 634056 KB Output is correct
28 Correct 1535 ms 584656 KB Output is correct
29 Correct 1618 ms 641556 KB Output is correct
30 Correct 2040 ms 656056 KB Output is correct
31 Correct 3580 ms 735832 KB Output is correct
32 Correct 4944 ms 723784 KB Output is correct
33 Correct 4577 ms 645288 KB Output is correct
34 Execution timed out 5068 ms 841268 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 5 ms 14940 KB Output is correct
4 Correct 464 ms 67100 KB Output is correct
5 Correct 506 ms 68728 KB Output is correct
6 Correct 731 ms 75360 KB Output is correct
7 Correct 658 ms 77380 KB Output is correct
8 Correct 605 ms 77628 KB Output is correct
9 Correct 575 ms 77384 KB Output is correct
10 Correct 589 ms 77376 KB Output is correct
11 Correct 549 ms 77484 KB Output is correct
12 Correct 683 ms 77380 KB Output is correct
13 Correct 506 ms 77388 KB Output is correct
14 Correct 155 ms 27096 KB Output is correct

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14696 KB Output is correct
4 Correct 3 ms 14936 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 3 ms 14940 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 3 ms 14940 KB Output is correct
14 Correct 3 ms 14940 KB Output is correct
15 Correct 4 ms 15196 KB Output is correct
16 Correct 4 ms 15196 KB Output is correct
17 Correct 4 ms 15196 KB Output is correct
18 Correct 4 ms 14940 KB Output is correct
19 Correct 4 ms 14940 KB Output is correct
20 Correct 4 ms 15196 KB Output is correct
21 Correct 3 ms 14940 KB Output is correct
22 Correct 4 ms 14940 KB Output is correct
23 Correct 4 ms 14936 KB Output is correct
24 Correct 3 ms 14940 KB Output is correct
25 Correct 3 ms 14988 KB Output is correct
26 Correct 3 ms 14940 KB Output is correct
27 Correct 3 ms 14940 KB Output is correct
28 Correct 3 ms 14940 KB Output is correct
29 Correct 4 ms 14904 KB Output is correct
30 Correct 7 ms 15704 KB Output is correct
31 Correct 7 ms 15340 KB Output is correct
32 Correct 8 ms 15708 KB Output is correct
33 Correct 8 ms 15452 KB Output is correct
34 Correct 9 ms 15452 KB Output is correct
35 Correct 7 ms 15452 KB Output is correct
36 Correct 7 ms 15596 KB Output is correct
37 Correct 7 ms 15708 KB Output is correct
38 Correct 36 ms 26332 KB Output is correct
39 Correct 37 ms 26452 KB Output is correct
40 Correct 35 ms 26716 KB Output is correct
41 Correct 24 ms 25980 KB Output is correct
42 Correct 25 ms 25688 KB Output is correct
43 Correct 25 ms 25948 KB Output is correct
44 Correct 18 ms 19992 KB Output is correct
45 Correct 18 ms 19548 KB Output is correct
46 Correct 26 ms 20316 KB Output is correct
47 Correct 12 ms 19036 KB Output is correct
48 Correct 11 ms 18268 KB Output is correct
49 Correct 14 ms 20060 KB Output is correct
50 Correct 6 ms 15452 KB Output is correct
51 Correct 6 ms 15452 KB Output is correct
52 Correct 7 ms 15452 KB Output is correct
53 Correct 6 ms 15452 KB Output is correct
54 Correct 6 ms 15508 KB Output is correct
55 Correct 6 ms 15452 KB Output is correct
56 Correct 5 ms 14940 KB Output is correct
57 Correct 3 ms 14940 KB Output is correct
58 Correct 13 ms 15448 KB Output is correct
59 Correct 3 ms 14940 KB Output is correct
60 Correct 3 ms 14940 KB Output is correct
61 Correct 5 ms 14940 KB Output is correct
62 Runtime error 3073 ms 1048576 KB Execution killed with signal 9
63 Halted 0 ms 0 KB -