Submission #1083945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083945		dwuy	Tourism (JOI23_tourism)	C++14	100 / 100	660 ms	29268 KiB

tourism

/**         - dwuy -

　　　　　 ／＞　   フ
　　　　　 | 　_　 _|
　 　　　 ／`ミ _x ノ
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

**/
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "test"
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;

struct BIT{
    int n;
    vector<int> tree;

    BIT(int n = 0){
        this-> n = n;
        this->tree.assign(n + 5, 0);
    }

    void update(int idx, int val){
        for(; idx; idx-=-idx&idx) tree[idx] += val;
    }

    int get(int idx){
        int res = 0;
        for(; idx<=n; idx+=-idx&idx) res += tree[idx];
        return res;
    }
};

const int MX = 100005;
int n, m, q;
int c[MX];
int ans[MX];
vector<int> G[MX];
vector<pii> Q[MX];

void nhap(){
    cin >> n >> m >> q;
    for(int i=1; i<n; i++){
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=1; i<=m; i++) cin >> c[i];
    for(int i=1; i<=q; i++){
        int l, r;
        cin >> l >> r;
        Q[r].push_back({l, i});
    }
}

namespace yingbao{
    int dfsID = 0;
    int p[MX];
    int h[MX];
    int num[MX];
    int head[MX];
    int numC[MX];
    int heavy[MX];
    
    int nxt[MX];
    int value[MX];
    BIT bit(MX);
    set<int> pos;

    void dfs(int u){
        h[u] = h[p[u]] + 1;
        numC[u] = 1;
        for(int v: G[u]) if(v != p[u]){
            p[v] = u;
            dfs(v);
            numC[u] += numC[v];
            if(numC[heavy[u]] < numC[v]) heavy[u] = v;
        }
    }

    void decompose(int u, int head){
        yingbao::head[u] = head;
        num[u] = ++dfsID;
        if(heavy[u]) decompose(heavy[u], head);
        for(int v: G[u]) if(v != heavy[u] && v != p[u]){
            decompose(v, v);
        }
    }

    void build(){
        dfs(1);
        decompose(1, 1);
    }

    void azzign(int l, int r, int id){
        for(auto itr = pos.lower_bound(l); itr != pos.end() && nxt[*itr] <= r;){
            int u = *itr, v = nxt[*itr];   
            bit.update(value[u], -(v - u + 1));
            nxt[u] = value[u] = 0;
            itr++;
            pos.erase(prev(itr));
        }
        
        auto itr = pos.lower_bound(l);
        if(itr != pos.begin() && nxt[*prev(itr)] >= l){
            itr--;
            bit.update(value[*itr], -(nxt[*itr] - l + 1));
            nxt[*itr] = l - 1; 
        }

        itr = pos.lower_bound(l);
        if(itr != pos.end() && *itr <= r){
            bit.update(value[*itr], -(r - *itr + 1));
            nxt[r + 1] = nxt[*itr];
            value[r + 1] = value[*itr];
            pos.erase(itr);
            pos.insert(r + 1);
        }
        bit.update(id, r - l + 1);
        pos.insert(l);
        nxt[l] = r;
        value[l] = id;
    }

    void update(int u, int v, int id){
        while(head[u] != head[v]){
            if(h[head[u]] < h[head[v]]) swap(u, v);
            azzign(num[head[u]], num[u], id);
            u = p[head[u]];
        }
        if(num[u] > num[v]) swap(u, v);
        azzign(num[u], num[v], id);
    }

    int get(int x){
        return bit.get(x + 1);
    }
}

void solve(){
    yingbao::build();
    c[0] = c[1];
    for(int i=1; i<=m; i++){
        yingbao::update(c[i-1], c[i], i);
        for(pii &qr: Q[i]){
            int l, id;
            tie(l, id) = qr;
            ans[id] = l != i? yingbao::get(l) : 1;
        }
    }
    for(int i=1; i<=q; i++) cout << ans[i] << endl;
}

int32_t main(){
    fastIO;
    //file(TASK);

    nhap();
    solve();

    return 0;
}

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