답안 #916665

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
916665	2024-01-26T08:59:30 Z	thangdz2k7	Tourism (JOI23_tourism)	C++17	7 / 100	162 ms	30292 KB

tourism

#include <bits/stdc++.h>
#define ii pair <int, int>
#define iii pair <ii, int>
#define F first
#define S second
#define pb push_back

using namespace std;

const int N = 1e5 + 5;

int n, m, q;
int c[N], l[N], r[N];
vector <int> adj[N], query[N];

int bit[N];

void update(int u, int v){
    while (u <= m){
        bit[u] += v;
        u += (u & (-u));
    }
}

int get(int u){
    int ans = 0;
    while (u > 0){
        ans += bit[u];
        u -= (u & (-u));
    }

    return ans;
}

int par[N], heavy[N], depth[N];

int dfs(int u, int pa){
    int sz = 0;
    par[u] = pa;
    int maxsz = 0;
    depth[u] = depth[pa] + 1;

    for (int v : adj[u]){
        if (v == pa) continue;
        int cur = dfs(v, u);
        sz += cur;
        if (maxsz < cur){
            cur = maxsz;
            heavy[u] = v;

        }
    }

    return sz;
}

int pos[N], head[N], cu;
set <ii> s;

void decompose(int u, int h){
    head[u] = h;
    ++ cu;
    pos[u] = cu;
    s.insert(ii(cu, cu));

    if (heavy[u]){
        decompose(heavy[u], h);
    }

    for (int v : adj[u]){
        if (v != par[u] && v != heavy[u]) decompose(v, v);
    }
}

int cur[N];

void add(int t, int l, int r, int val){
    while (true){
        ii z = *s.lower_bound(ii(l, -1));
        if (z.F > r) break;
        s.erase(z);
        if (z.S > r) {
            s.insert(ii(r + 1, z.S));
            int le = r - z.F + 1;
            update(cur[z.F] + 1, le);
            update(val + 1, -le);
            cur[r + 1] = cur[z.F];
        }
        else {
            int le = z.S - z.F + 1;
            update(cur[z.F] + 1, le);
            update(val + 1, -le);
        }
    }

    ii z = *(--s.lower_bound(ii(l, -1)));
    if (z.S > r){
        s.erase(z);
        s.insert(ii(z.F, l - 1));
        s.insert(ii(r + 1, z.S));
        int le = r - l + 1;
        update(cur[z.F] + 1, le);
        update(val + 1, -le);
    }

    else if (z.S >= l){
         s.erase(z);
         s.insert(ii(z.F, l - 1));
         int le = z.S - l + 1;
         update(cur[z.F] + 1, le);
         update(val + 1, -le);
    }

    s.insert(ii(l, r));
    cur[l] = val;
}

void upd(int u, int v, int val){
//    for (; head[u] != head[v]; v = par[head[v]]){
//        if (depth[head[u]] > depth[head[v]]) swap(u, v);
//        add(head[v], pos[head[v]], pos[v], val);
//
//    }

    if (depth[u] > depth[v]) swap(u, v);
    add(head[u], pos[u], pos[v], val);
}

int ans[N];

void solve(){
    cin >> n >> m >> q;
    for (int i = 1, u, v; i <= n - 1; ++ i){
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    for (int i = 1; i <= m; ++ i) cin >> c[i];
    for (int i = 1, r; i <= q; ++ i){
        cin >> l[i] >> r;
        query[r].pb(i);
    }

    dfs(1, 0);
    decompose(1, 1);

    s.insert(ii(0, 0)), s.insert(ii(n + 1, n + 1));

    for (int i = 1; i <= m; ++ i){
        if (i > 1) upd(c[i], c[i - 1], i - 1);
        for (int k : query[i]){
            ans[k] = max(1, get(l[k]));
        }
    }

    for (int i = 1; i <= q; ++ i) cout << ans[i] << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();
    return 0;
}

Subtask #1
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	8540 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	8540 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	8540 KB	Output is correct
2	Correct	2 ms	8540 KB	Output is correct
3	Correct	3 ms	8540 KB	Output is correct
4	Correct	90 ms	19668 KB	Output is correct
5	Correct	100 ms	25172 KB	Output is correct
6	Correct	105 ms	27220 KB	Output is correct
7	Correct	139 ms	30292 KB	Output is correct
8	Correct	147 ms	30284 KB	Output is correct
9	Correct	136 ms	30152 KB	Output is correct
10	Correct	133 ms	30292 KB	Output is correct
11	Correct	162 ms	30124 KB	Output is correct
12	Correct	135 ms	28880 KB	Output is correct
13	Correct	132 ms	28936 KB	Output is correct
14	Correct	136 ms	28756 KB	Output is correct
15	Correct	54 ms	26828 KB	Output is correct
16	Correct	131 ms	30036 KB	Output is correct
17	Correct	46 ms	12620 KB	Output is correct