oj.uz

Submission #1037708

# Submission time Handle Problem Language Result Execution time Memory
1037708 2024-07-29T07:08:13 Z 정민찬(#10982) Tourism (JOI23_tourism) C++17
0 / 100
 3295 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<pair<int,int>> tree;
    void init(int n) {
        int sz = 1 << __lg(n-1) + 2;
        tree.resize(sz);
        build(1, 1, n);
    }
    void build(int node, int s, int e) {
        if (s == e) {
            tree[node] = {-inf, s};
            return;
        }
        int mid = s + e >> 1;
        build(node*2, s, mid);
        build(node*2+1, mid+1, e);
        tree[node] = max(tree[node*2], tree[node*2+1]);
    }
    void update(int node, int s, int e, int tar, int val, int num = -1) {
        if (s > tar || tar > e) return;
        if (s == e) {
            if (num == -1) num = s;
            tree[node] = {val, num};
            return;
        }
        int mid = s + e >> 1;
        update(node*2, s, mid, tar, val, num);
        update(node*2+1, mid+1, e, tar, val, num);
        tree[node] = max(tree[node*2], tree[node*2+1]);
    }
    pair<int,int> query(int node, int s, int e, int l, int r) {
        if (l > e || s > r) return {-inf, -1};
        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], Idx(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).first;
        int ret2 = -mns.query(1, 1, D.size(), li, ri).first;
        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];
    }
    vector<int> Sum(N+1, 0);
    for (int i=1; i<=N; i++) {
        sort(s[i].begin(), s[i].end());
        Sum[i] = Sum[i-1] + s[i].size();
    }
    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::build(int, int, int)':
tourism.cpp:74:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         int mid = s + e >> 1;
      |                   ~~^~~
tourism.cpp: In member function 'void MaxSegmentTree::update(int, int, int, int, int, int)':
tourism.cpp:86:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |         int mid = s + e >> 1;
      |                   ~~^~~
tourism.cpp: In member function 'std::pair<int, int> MaxSegmentTree::query(int, int, int, int, int)':
tourism.cpp:94:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |         int mid = s + e >> 1;
      |                   ~~^~~
tourism.cpp: In function 'void dnc(int, std::vector<int>)':
tourism.cpp:209:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  209 |     for (int i=0; i<adj[x].size(); i++) {
      |                   ~^~~~~~~~~~~~~~
tourism.cpp:241:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  241 |     for (int i=1; i<=D.size(); i++) {
      |                   ~^~~~~~~~~~
tourism.cpp:245:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  245 |         while (j < curq.size() && L[curq[j]] == D[i-1]) {
      |                ~~^~~~~~~~~~~~~
tourism.cpp:250:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  250 |     for (int i=0; i<=D.size() + 2; i++) {
      |                   ~^~~~~~~~~~~~~~
tourism.cpp:254:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  254 |     for (int i=0; i<adj[x].size(); i++) {
      |                   ~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Incorrect 3 ms 14940 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Incorrect 3 ms 14940 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 4 ms 14940 KB Output is correct
3 Correct 5 ms 15196 KB Output is correct
4 Runtime error 3295 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 14680 KB Output is correct
2 Correct 166 ms 41156 KB Output is correct
3 Correct 258 ms 57544 KB Output is correct
4 Correct 200 ms 49392 KB Output is correct
5 Correct 333 ms 65116 KB Output is correct
6 Correct 336 ms 65480 KB Output is correct
7 Correct 357 ms 65324 KB Output is correct
8 Correct 305 ms 63940 KB Output is correct
9 Correct 346 ms 65764 KB Output is correct
10 Correct 312 ms 65480 KB Output is correct
11 Correct 328 ms 64096 KB Output is correct
12 Correct 352 ms 66248 KB Output is correct
13 Incorrect 524 ms 64688 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
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 15020 KB Output is correct
4 Incorrect 565 ms 69204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Incorrect 3 ms 14940 KB Output isn't correct
5 Halted 0 ms 0 KB -