제출 #823685

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
823685		thimote75	Tourism (JOI23_tourism)	C++14	59 / 100	5081 ms	69372 KiB

tourism

#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using iset  = set<int>;
using igrid = vector<idata>;

using t_road  = pair<int, int>;
using t_roads = vector<t_road>;
using t_graph = vector<t_roads>;

using di = pair<int, int>;
using vd = vector<di>;

const int MAXK = 20;

struct Tree {
    igrid roads;

    idata preordre, postordre, parents, depth;
    igrid eulertour;
    igrid parents_2k;

    void dfs (int node, int parent, int _depth, int &iOrdre) {
        preordre[node] = iOrdre ++;
        parents [node] = parent;
        depth   [node] = _depth;

        for (int next : roads[node]) if (next != parent) {
            eulertour[node].push_back(iOrdre ++);
            dfs(next, node, _depth + 1, iOrdre);
        }
        
        postordre[node] = iOrdre ++;
    }

    Tree (int N, igrid &roads) : roads(roads) {
        eulertour.resize(N);
        postordre.resize(N);
        preordre .resize(N);
        parents  .resize(N);
        depth    .resize(N);

        int iOrdre = 0;
        dfs (0, -1, 0, iOrdre);

        parents_2k.resize(N, idata(MAXK, -1));

        for (int i = 0; i < N; i ++) parents_2k[i][0] = parents[i];

        for (int k = 0; k + 1 < MAXK; k ++) {
            for (int i = 0; i < N; i ++) {
                if (parents_2k[i][k] == -1) continue ;

                parents_2k[i][k + 1] = parents_2k[parents_2k[i][k]][k];
            }
        }
    }

    int jump (int node, int k) {
        for (int i = 0; i < MAXK; i ++)
            if ((1 << i) & k)
                node = parents_2k[node][i];
        
        return node;
    }
    int lca (int a, int b) {
        if (depth[a] > depth[b]) swap(a, b);

        b = jump(b, depth[b] - depth[a]);
        if (a == b) return a;

        for (int i = MAXK - 1; i >= 0; i --) {
            if (parents_2k[a][i] == parents_2k[b][i]) continue ;

            a = parents_2k[a][i];
            b = parents_2k[b][i];
        }

        if (a == b) return a;
        return parents[a];
    }
};

struct VirtualTree {
    int size = 1;
    t_graph roads;
    map<int, int> id_to_vid;

    int get (int node) {
        return (*id_to_vid.find(node)).second;
    }

    idata L;
    idata R;
    idata C;

    pair<int, int> dfs (int node, int parent, int coming) {
        C[node] = coming;
        for (const auto road : roads[node]) if (road.first != parent) {
            const auto data = dfs(road.first, node, road.second);

            L[node] = max(L[node], data.first);
            R[node] = min(R[node], data.second);
        }

        return { L[node], R[node] };
    }

    VirtualTree (Tree &tree, iset virtual_set) {
        vd order_positions;
        for (int u : virtual_set) order_positions.push_back({ tree.preordre[u], u });

        sort(order_positions.begin(), order_positions.end());

        for (int i = 0; i + 1 < order_positions.size(); i ++){
            int u = order_positions[i    ].second;
            int v = order_positions[i + 1].second;

            int l = tree.lca(u, v);
            virtual_set.insert(l);
        }

        vd dist_computations;
        for (int u : virtual_set) {
            dist_computations.push_back({ tree.preordre [u], u }); 
            for (int h : tree.eulertour[u])
                dist_computations.push_back({ h, u });
            dist_computations.push_back({ tree.postordre[u], u }); 
        }

        sort(dist_computations.begin(), dist_computations.end());

        set<pair<int, int>> pot_roads;

        for (int i = 0; i + 1 < dist_computations.size(); i ++) {
            int u = dist_computations[i]    .second;
            int v = dist_computations[i + 1].second;

            if (u == v) continue ;
            pot_roads.insert({ min(u, v), max(u, v) });
        }

        int iNode = 0;
        for (int u : virtual_set)
            id_to_vid.insert({ u, iNode ++ });
        
        roads.resize(virtual_set.size());
        for (const auto &road : pot_roads) {
            int u = road.first; int v = road.second;
            int dist = abs(tree.depth[u] - tree.depth[v]);

            size += dist;

            u = get(u); v = get(v);
            roads[u].push_back({ v, dist });
            roads[v].push_back({ u, dist });
        }

        L.resize(virtual_set.size(), - 1e9);
        R.resize(virtual_set.size(),   1e9);
        C.resize(virtual_set.size());
    }
};

struct Query {
    int l, r;
    int answer;

    int order (int mid) {
        if (r < mid) return -1;
        if (l > mid) return 1;
        return 0;
    }
};

struct SegTree {
    vector<int> tree;

    int start, height, size;

    SegTree () = default;
    SegTree (int _size) {
        size   = _size;
        height = ceil(log2(size));
        start  = 1 << height;

        tree.resize(start << 1);
    }
    int _query (int node) {
        if (node == 0) return 0;

        return tree[node] + _query(node >> 1);
    }
    int query (int node) {
        return _query(node + start);
    }
    void add (int l, int r, int x) {
        l += start; r += start;

        while (l < r) {
            if ((l & 1) == 1) tree[l] += x;
            if ((r & 1) == 0) tree[r] += x;

            l = (l + 1) >> 1;
            r = (r - 1) >> 1;
        }

        if (l == r) tree[l] += x;
    }
};

const int MAXS = 2e5;

SegTree stree(MAXS);

using Point = pair<int, pair<int, int>>;

struct QueryManager {
    static void solve (vector<Query*> queries, vector<Point> points) {
        sort(points.begin(), points.end());

        vd queries_time;
        for (int i = 0; i < queries.size(); i ++)
            queries_time.push_back({ queries[i]->r, i });
        sort(queries_time.begin(), queries_time.end());

        for (int iOP = 0; iOP < points.size(); iOP ++)
            stree.add(0, max(-1, points[iOP].second.first), points[iOP].second.second);
        
        int bonus = 0;
        int iOP = 0;
        for (int iQ = 0; iQ < queries.size(); iQ ++) {
            int time = queries_time[iQ].first;
            int quid = queries_time[iQ].second;

            while (iOP != points.size() && time >= points[iOP].first) {
                stree.add(0, max(-1, points[iOP].second.first), - points[iOP].second.second);
                bonus += points[iOP].second.second;
                iOP ++;
            }

            queries[quid]->answer = bonus + stree.query(queries[quid]->l);
        }

        for (; iOP < points.size(); iOP ++)
            stree.add(0, max(-1, points[iOP].second.first), - points[iOP].second.second);
    }
};

VirtualTree create (Tree &tree, idata &R, int left, int right, int mid) {
    iset values;
    for (int u = left; u <= right; u ++)
        values.insert(R[u]);
    
    VirtualTree vt (tree, values);

    for (int u = left; u <= mid; u ++)
        vt.L[vt.get(R[u])] = u;
    for (int u = right; u >= mid; u --)
        vt.R[vt.get(R[u])] = u;
    
    vt.dfs(vt.get(R[mid]), -1, 1);

    return vt;
}

void solve (Tree &tree, idata &R, int l, int r, vector<Query*> queries) { // [l; r]
    if (queries.size() == 0) return ;

    int mid = (l + r) >> 1;
    VirtualTree vt = create(tree, R, l, r, mid);

    vector<Query*> left_q, right_q;
    vector<Query*> mid_q;
    vector<Point> points;
    for (int i = 0; i < vt.L.size(); i ++)
        points.push_back({ vt.R[i], { vt.L[i], vt.C[i] } });
    for (Query* q : queries) {
        int o = q->order(mid);
        if (o == -1)  left_q.push_back(q);
        if (o ==  1) right_q.push_back(q);

        if (o == 0) {
            mid_q.push_back(q);
        }
    }

    QueryManager::solve(mid_q, points);

    solve(tree, R, l, mid - 1, left_q);
    solve(tree, R, mid + 1, r, right_q);
}

int main () {
    int N, M, Q;
    cin >> N >> M >> Q;

    igrid roads(N);
    for (int i = 1; i < N; i ++) {
        int a, b;
        cin >> a >> b;
        a --; b --;

        roads[a].push_back(b);
        roads[b].push_back(a);
    }

    Tree tree(N, roads);

    idata R(M);
    for (int i = 0; i < M; i ++) {
        cin >> R[i];
        R[i] --;
    }

    vector<Query*> queries;
    
    for (int q = 0; q < Q; q ++) {
        int l, r;
        cin >> l >> r;
        l --; r --;

        Query* qu = new Query();
        qu->l = l; qu->r = r;
        queries.push_back(qu);
    }

    solve(tree, R, 0, M - 1, queries);

    for (Query* q : queries) {
        cout << q->answer << "\n";
        delete q;
    }
}

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

tourism.cpp: In constructor 'VirtualTree::VirtualTree(Tree&, iset)':
tourism.cpp:118:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for (int i = 0; i + 1 < order_positions.size(); i ++){
      |                         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:138:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         for (int i = 0; i + 1 < dist_computations.size(); i ++) {
      |                         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp: In static member function 'static void QueryManager::solve(std::vector<Query*>, std::vector<std::pair<int, std::pair<int, int> > >)':
tourism.cpp:226:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  226 |         for (int i = 0; i < queries.size(); i ++)
      |                         ~~^~~~~~~~~~~~~~~~
tourism.cpp:230:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  230 |         for (int iOP = 0; iOP < points.size(); iOP ++)
      |                           ~~~~^~~~~~~~~~~~~~~
tourism.cpp:235:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  235 |         for (int iQ = 0; iQ < queries.size(); iQ ++) {
      |                          ~~~^~~~~~~~~~~~~~~~
tourism.cpp:239:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  239 |             while (iOP != points.size() && time >= points[iOP].first) {
      |                    ~~~~^~~~~~~~~~~~~~~~
tourism.cpp:248:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  248 |         for (; iOP < points.size(); iOP ++)
      |                ~~~~^~~~~~~~~~~~~~~
tourism.cpp: In function 'void solve(Tree&, idata&, int, int, std::vector<Query*>)':
tourism.cpp:279:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  279 |     for (int i = 0; i < vt.L.size(); i ++)
      |                     ~~^~~~~~~~~~~~~

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