oj.uz

Submission #947433

# Submission time Handle Problem Language Result Execution time Memory
947433 2024-03-16T07:13:39 Z weakweakweak Capital City (JOI20_capital_city) C++17
30 / 100
 180 ms 94932 KB 
//好吧，我很笨
#include <bits/stdc++.h>
using namespace std;

int lt[510000], rt[510000], cnt[510000], n, k, col[510000], revlt[510000], now = 0, l[510000], r[510000];
int pos[510000] = {0};

vector<int> e[510000];
vector<int> qs[510000];
set<int> st[510000];

int a[510000] = {0};
void update (int i, int val) {
    for (; i <= n; i += i & -i) a[i] += val;
}
int query (int i) {
    int res = 0;
    for (; i > 0; i -= i & -i) res += a[i];
    return res;
}
int query2 (int l, int r) {return query(r) - query(l - 1);}


void dfs (int i, int par) {
    lt[i] = ++now, revlt[now] = i;
    for (int j : e[i]) if (j != par) dfs(j, i);
    rt[i] = now;
}




struct SEGMN {
    int a[810000];
    void build (int lr, int rr, int id) {
        if (lr == rr) {
            a[id] = l[col[lr]];
            return;
        }
        int mid = (lr + rr) / 2;
        build (lr, mid, id << 1); build(mid + 1, rr, id << 1 | 1);
        a[id] = min(a[id << 1], a[id << 1 | 1]);
    }
    int query (int lr, int rr, int ql, int qr, int id) {
        if (ql <= lr and rr <= qr) return a[id];
        int res = INT_MAX, mid = (lr + rr) / 2;
        if (ql <= mid) res = min(res, query(lr, mid, ql, qr, id << 1));
        if (qr > mid ) res = min(res, query(mid + 1, rr, ql, qr, id << 1 | 1));
        return res;
    }
} segl;



struct SEGMX {
    int a[810000];
    void build (int lr, int rr, int id) {
        if (lr == rr) {
            a[id] = r[col[lr]];
            return;
        }
        int mid = (lr + rr) / 2;
        build (lr, mid, id << 1); build(mid + 1, rr, id << 1 | 1);
        a[id] = max(a[id << 1], a[id << 1 | 1]);
    }
    int query (int lr, int rr, int ql, int qr, int id) {
        if (ql <= lr and rr <= qr) return a[id];
        int res = -1, mid = (lr + rr) / 2;
        if (ql <= mid) res = max(res, query(lr, mid, ql, qr, id << 1));
        if (qr > mid ) res = max(res, query(mid + 1, rr, ql, qr, id << 1 | 1));
        return res;
    }
} segr;

int main () {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    int rt = 1;
    for (int i = 1; i <= n; i++) if (e[i].size() == 1) rt = i;
    dfs(rt, rt);

    for (int i = 1; i <= n; i++) {
        cin >> col[lt[i]];
        if (cnt[col[lt[i]]]++ == 0) l[col[lt[i]]] = r[col[lt[i]]] = lt[i];
        else l[col[lt[i]]] = min(l[col[lt[i]]], lt[i]),  r[col[lt[i]]] = max(r[col[lt[i]]], lt[i]); 
    }

    for (int i = 1; i <= k; i++) {
        qs[r[i]].push_back(l[i]);
        st[r[i]] . insert(l[i]);
    }

    segl.build(1, n, 1);
    segr.build(1, n, 1);
    int ans = k;
    for (int i = 1; i <= n; i++) {
        if (pos[col[i]]) update(pos[col[i]], -1);
        pos[col[i]] = i;
        update(i, 1);
        for (int j : qs[i]) {
            int wow1 = segl.query(1, n, j, i, 1), wow2 = segr.query(1, n, j, i, 1);  
            if (wow1 >= j and wow2 <= i) ans = min(ans, query2(j, i));
            else if (st[wow2].count(wow1) == 0) {
                qs[wow2].push_back(wow1);
                st[wow2].insert(wow1);
            }
        }   
    }

    cout << ans - 1 << '\n';
return 0;}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 65884 KB Output is correct
2 Correct 13 ms 66140 KB Output is correct
3 Correct 13 ms 65880 KB Output is correct
4 Correct 13 ms 66132 KB Output is correct
5 Correct 12 ms 65880 KB Output is correct
6 Correct 12 ms 66140 KB Output is correct
7 Incorrect 13 ms 65884 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 65884 KB Output is correct
2 Correct 13 ms 66140 KB Output is correct
3 Correct 13 ms 65880 KB Output is correct
4 Correct 13 ms 66132 KB Output is correct
5 Correct 12 ms 65880 KB Output is correct
6 Correct 12 ms 66140 KB Output is correct
7 Incorrect 13 ms 65884 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 94640 KB Output is correct
2 Correct 117 ms 94540 KB Output is correct
3 Correct 167 ms 94540 KB Output is correct
4 Correct 123 ms 94932 KB Output is correct
5 Correct 163 ms 94028 KB Output is correct
6 Correct 136 ms 94292 KB Output is correct
7 Correct 155 ms 93332 KB Output is correct
8 Correct 114 ms 93268 KB Output is correct
9 Correct 128 ms 90708 KB Output is correct
10 Correct 126 ms 94620 KB Output is correct
11 Correct 132 ms 94292 KB Output is correct
12 Correct 135 ms 94376 KB Output is correct
13 Correct 133 ms 94552 KB Output is correct
14 Correct 136 ms 94332 KB Output is correct
15 Correct 143 ms 94344 KB Output is correct
16 Correct 141 ms 94288 KB Output is correct
17 Correct 131 ms 94204 KB Output is correct
18 Correct 128 ms 94184 KB Output is correct
19 Correct 136 ms 94328 KB Output is correct
20 Correct 136 ms 94296 KB Output is correct
21 Correct 13 ms 66136 KB Output is correct

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 65884 KB Output is correct
2 Correct 13 ms 66140 KB Output is correct
3 Correct 13 ms 65880 KB Output is correct
4 Correct 13 ms 66132 KB Output is correct
5 Correct 12 ms 65880 KB Output is correct
6 Correct 12 ms 66140 KB Output is correct
7 Incorrect 13 ms 65884 KB Output isn't correct
8 Halted 0 ms 0 KB -