제출 #969917

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
969917		efedmrlr	Tourism (JOI23_tourism)	C++17	100 / 100	1132 ms	64432 KiB

tourism

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 1e5+5;
const int ALPH = 26;
const int LGN = 20;
constexpr int MOD = 1e9+7;
array<int, 2 * N> lg2;
struct RMQ {
    array<vector<array<int, 2> >, LGN> st;
    void reset(vector<int> &x, vector<int> &y) {
        REP(i, LGN) st[i].assign(x.size(), {INF, INF});
        for(int i = 0; i < x.size(); i++) {
            st[0][i] = {y[x[i]], x[i]};
        }
        for(int k = 1; k < LGN; k++) {
            for(int i = 0; i < x.size(); i++) {
                if(i + (1 << (k - 1)) >= x.size()) break;
                st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
            }
        }
    }
    int query(int l, int r) {
        int k = lg2[r - l + 1];
        return min(st[k][l], st[k][r - (1 << k) + 1])[1];
    }
};

struct LCA {
    vector<int> tin, eul, dep;
    RMQ rm;
    int tim = 0;
    LCA() {
        tim = 0;
        eul.clear();
        tin.assign(N, 0);
        dep.assign(N, 0);
    }
    void prec(int node, int par, vector<vector<int> > &adj) {
        tin[node] = tim++;
        eul.pb(node);
        for(auto c : adj[node]) {
            if(c == par) continue;
            dep[c] = dep[node] + 1;
            prec(c, node, adj);
            eul.pb(node); tim++;
        }
    }
    void build() {
        rm.reset(eul, dep);
    }
    int query(int a, int b) {
        if(tin[a] > tin[b]) swap(a, b);
        return rm.query(tin[a], tin[b]);
    }

};

struct BIT {
    vector<int> st;
    int n;
    void reset(int sz) {
        n = sz;
        st.assign(sz + 3, 0);
    }
    void update(int ind, int val) {
        ind++;
        while(ind <= n) {
            st[ind] += val;
            ind += (ind) & (-ind);
        }
    }
    int getSum(int ind) {
        int ret = 0;
        ind++;
        while(ind > 0) {
            ret += st[ind];
            ind -= ind & (-ind);
        }
        return ret;
    }
};

int n,m,q;

vector<int> a(N, 0);
vector<vector<int> > occ(N, vector<int>());
vector<vector<int> > adj(N, vector<int>()), adj2(N, vector<int>());
LCA lca;
vector<int> res(N, 0);

void dfs(int node, int par, vector<array<int, 3> > &eg, int tm) {
    array<int, 3> ed = {0, INF, 0}; // x, y, w
    if(node != par) {
        ed[2] = abs(lca.dep[node] - lca.dep[par]);
    }
    for(auto c : adj2[node]) {
        if(c == par) continue;
        dfs(c, node, eg, tm);
        ed[0] = max(ed[0], eg.back()[0]);
        ed[1] = min(ed[1], eg.back()[1]);
    }
    auto itr = lower_bound(all(occ[node]), tm);
    if(itr != occ[node].end())ed[1] = min(ed[1], *itr);
    itr = lower_bound(all(occ[node]), tm);
    if(itr != occ[node].begin()) {
        itr--;
        ed[0] = max(ed[0], *itr);
    }
    if(node != par) eg.pb(ed);
}

void dnc(int tl, int tr, vector<array<int, 3> > &qu) {
    // cout << "tl:" << tl << " tr:" << tr << endl;
    if(tl > tr || qu.empty()) return;
    if(tl == tr) {
        return;
    }
    int tm = (tl + tr) >> 1;
    vector<array<int, 3> > cur, lf, rg;
    for(auto &c : qu) {
        if(c[0] > tm) {
            rg.pb(c);
        }
        else if(c[1] < tm) {
            lf.pb(c);
        }
        else {
            cur.pb(c);
        }
    }
    dnc(1, tm - 1, lf); dnc(tm + 1, tr, rg);
    if(cur.empty()) return;
    // cout << "tl:" << tl << " tr:" << tr << endl;
    vector<array<int, 3> > eg;
    // Virt Tree
    vector<int> vtr;
    for(int i = tl; i <= tr; i++) {
        vtr.pb(a[i]);
    }
    sort(all(vtr), [](int u, int v) {
        return lca.tin[u] < lca.tin[v];
    });
    vtr.resize(unique(all(vtr)) - vtr.begin());
    int sz = vtr.size();
    for(int i = 1; i < sz; i++) {
        vtr.pb(lca.query(vtr[i - 1], vtr[i]));
    }
    sort(all(vtr), [](int u, int v) {
        return lca.tin[u] < lca.tin[v];
    });
    vtr.resize(unique(all(vtr)) - vtr.begin());
    vector<int> stck;
    // assert(!vtr.empty());
    int rt = a[tm];
    
    stck.pb(vtr[0]);
    sz = vtr.size();
    for(auto c : vtr) {
        adj2[c].clear();
    }
    for(int i = 1; i < sz; i++) {
        while(lca.query(vtr[i], stck.back()) != stck.back()) {
            stck.pop_back();
        }
        adj2[stck.back()].pb(vtr[i]);
        adj2[vtr[i]].pb(stck.back());
        stck.pb(vtr[i]);
    }
    // for(auto c : vtr) {
    //     cout << c << " ";
    // }
    // cout << endl;
    dfs(rt, rt, eg, tm);
    for(auto &c : eg) {
        // assert(c[0] < tm && c[1] > tm);
        c[1] = min(c[1], tr + 1);
    }
    // take l <= x
    sort(rall(eg));
    sort(rall(cur));
    int ind = 0, sum = 0;
    for(auto &c : cur) {
        while(ind < eg.size() && eg[ind][0] >= c[0]) {
            sum += eg[ind][2];
            ind++;
        }
        res[c[2]] += sum;
    }

    // take l > x && r >= y
    reverse(all(eg));
    reverse(all(cur));
    BIT st;
    st.reset(tr - tm + 2);
    ind = 0;
    for(auto &c : cur) {
        while(ind < eg.size() && eg[ind][0] < c[0]) {
            st.update(eg[ind][1] - tm, eg[ind][2]);
            ind++;
        }
        res[c[2]] += st.getSum(c[1] - tm);
    }
}

inline void solve() {
    cin >> n >> m >> q;
    REP(i, n - 1) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    lca.prec(1, 0, adj);
    lca.build();
    for(int i = 1; i <= m; i++) {
        cin >> a[i];
        occ[a[i]].pb(i);
    }
    vector<array<int, 3> > qu(q);
    for(int i = 0; i < q; i++) {
        cin >> qu[i][0] >> qu[i][1];
        qu[i][2] = i;
    }

    dnc(1, m, qu);
    REP(i, q) {
        cout << res[i] + 1 << "\n";
    }

}
 
signed main() {
    lg2[1] = 0;
    for(int i = 2; i < 2 * N; i++) {
        lg2[i] = lg2[i >> 1] + 1;
    }
    fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

컴파일 시 표준 에러 (stderr) 메시지

tourism.cpp: In member function 'void RMQ::reset(std::vector<int>&, std::vector<int>&)':
tourism.cpp:33:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for(int i = 0; i < x.size(); i++) {
      |                        ~~^~~~~~~~~~
tourism.cpp:37:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             for(int i = 0; i < x.size(); i++) {
      |                            ~~^~~~~~~~~~
tourism.cpp:38:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |                 if(i + (1 << (k - 1)) >= x.size()) break;
      |                    ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
tourism.cpp: In function 'void dnc(int, int, std::vector<std::array<int, 3> >&)':
tourism.cpp:204:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  204 |         while(ind < eg.size() && eg[ind][0] >= c[0]) {
      |               ~~~~^~~~~~~~~~~
tourism.cpp:218:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  218 |         while(ind < eg.size() && eg[ind][0] < c[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