Submission #988411

#	Time	Username	Problem	Language	Result	Execution time	Memory
988411		Zero_OP	Tourism (JOI23_tourism)	C++14	100 / 100	1069 ms	26448 KiB

tourism

//no template practicing

#include<bits/stdc++.h>

using namespace std;

const int MAX = 1e5 + 5;
const int inf = 1e9;

int n, m, q, timer_hld, pos[MAX], c[MAX], sz[MAX], depth[MAX], par[MAX], head[MAX], answer[MAX];
vector<int> adj[MAX];
vector<pair<int, int>> queries[MAX];
int val[MAX];
map<int, int> cut;

struct Fenwick{
    vector<int> bit;
    Fenwick(int n) : bit(n + 3, 0) {}

    void update(int id, int val){
        id += 2;
        for(; id > 0; id -= id & (-id)){
            bit[id] += val;
        }
    }

    int query(int id){
        id += 2;
        int sum = 0;
        assert(id > 0);
        for(; id < (int)bit.size(); id += id & (-id)){
            sum += bit[id];
        }
        return sum;
    }
};

Fenwick T(0);

void modify(int l, int r, int x){
    for(int p : {l, r}){
        if(cut.find(p) == cut.end()){
            auto iter = cut.lower_bound(p);
            int k = prev(iter) -> second;
            cut[p] = k;
        }
    }

    while(true){
        auto iter = cut.lower_bound(l);
        int u = iter -> first;
        if(u == r) break;
        int v = next(iter) -> first;
        int w = iter -> second;
        T.update(w, -(v - u));
        cut.erase(iter);
    }

    cut[l] = x;
    T.update(x, r - l);

    for(int p : {l, r}){
        auto iter = cut.lower_bound(p);
        if(iter != cut.begin() && (iter -> second) == (prev(iter) -> second)){
            cut.erase(iter);
        }
    }
}

void update_path(int u, int v, int w){
    while(head[u] != head[v]){
        if(depth[head[u]] < depth[head[v]]) swap(u, v);
        modify(pos[head[u]], pos[u] + 1, w);
        u = par[head[u]];
    }

    if(pos[u] > pos[v]) swap(u, v);
    modify(pos[u], pos[v] + 1, w);
}

int calculate(int L){
    return T.query(L);
}

void dfs_sz(int u){
    sz[u] = 1;
    for(int &v : adj[u]){
        adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
        depth[v] = depth[u] + 1;
        par[v] = u;
        dfs_sz(v);
        sz[u] += sz[v];
        if(sz[adj[u][0]] < sz[v]){
            swap(v, adj[u][0]);
        }
    }
}

void dfs_hld(int u, int top){
    head[u] = top;
    pos[u] = timer_hld++;

    for(int v : adj[u]){
        if(v == adj[u][0]) dfs_hld(v, top);
        else dfs_hld(v, v);
    }
}

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

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

    for(int i = 0; i < m; ++i){
        cin >> c[i]; --c[i];
    }

    for(int i = 0; i < q; ++i){
        int l, r;
        cin >> l >> r;
        --l, --r;
        if(l == r){
            answer[i] = 1;
            continue;
        }
        queries[r].push_back({l, i});
    }

    dfs_sz(0);
    dfs_hld(0, 0);

    T = Fenwick(m);
    cut[0] = -1;
    cut[n] = -1;

    update_path(c[0], c[0], 0);
    for(int i = 1; i < m; ++i){
        update_path(c[i - 1], c[i], i - 1); //change value of every edges from c[i - 1] to c[i] to i - 1
        update_path(c[i], c[i], i); //change the value of vertex c[i] to i

        for(auto [j, id] : queries[i]){
            answer[id] = calculate(j); //number of edges have value >= j
        }
    }

    for(int i = 0; i < q; ++i){
        cout << answer[i] << '\n';
    }

    return 0;
}

Compilation message (stderr)

tourism.cpp: In function 'int main()':
tourism.cpp:149:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  149 |         for(auto [j, id] : queries[i]){
      |                  ^

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41