제출 #434346

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434346		cuom1999	늑대인간 (IOI18_werewolf)	C++14	15 / 100	4097 ms	166408 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> lab;
    DSU(int n) {
        lab.assign(n + 1, -1);
    }

    int merge(int a, int b) {
        if (lab[a] > lab[b]) {
            swap(a, b);
        }
        lab[a] += lab[b];
        lab[b] = a;
        return a;
    }

    int getRoot(int a) {
        while (lab[a] >= 0) a = lab[a];
        return a;
    }
};

struct DSUTree {
    struct Node {
        int tin, tout, weight;
        vector<int> child;
    };

    int n, TIME = 0;
    vector<array<int, 3>> edges;
    vector<int> root, eulerTour;
    vector<vector<int>> par;
    vector<Node> nodes;
    
    DSUTree(int n): n(n) {
        root.resize(n + 1);
        nodes.resize(2 * n);
        par.assign(2 * n, vector<int>(20));
    }

    void addEdge(int u, int v, int c) {
        edges.push_back({c, u, v});
    }

    void construct() {
        sort(edges.begin(), edges.end());
        DSU dsu(n);

        for (int i = 1; i <= n; i++) {
            root[i] = i;
            nodes[i].weight = -1e9;
        }

        int cnt = n;
        for (auto e: edges) {
            int a = dsu.getRoot(e[1]);
            int b = dsu.getRoot(e[2]);
            if (a == b) continue;

            int root1 = root[a], root2 = root[b];
            a = dsu.merge(a, b);
            root[a] = ++cnt;
            nodes[cnt].child.push_back(root1);
            nodes[cnt].child.push_back(root2);
            nodes[cnt].weight = e[0];

            par[root1][0] = cnt;
            par[root2][0] = cnt;
        }

        dfs(2 * n - 1);
        getOrder();

        for (int i = 1; i < 20; i++) {
            for (int j = 1; j <= 2 * n - 1; j++) {
                par[j][i] = par[par[j][i - 1]][i - 1];
            }
        }
    }

    void dfs(int u) {
        nodes[u].tin = ++TIME;
        eulerTour.push_back(u);
        for (auto i: nodes[u].child) {
            dfs(i);
        }
        nodes[u].tout = ++TIME;
        eulerTour.push_back(u);
    }

    vector<int> order;
    void getOrder() {
        vector<int> vs(2 * n + 1);
        for (auto i: eulerTour) {
            if (i <= n && vs[i] == 0) {
                order.push_back(i);
            }
            vs[i] = 1;
        }
    }

    // return the interval that s can reach through edges <= r
    pair<int, int> getInterval(int s, int r) {
        // find farthest parent has weight <= r
        for (int i = 19; i >= 0; i--) {
            int p = par[s][i];
            if (p && nodes[p].weight <= r) {
                s = p;
            }
        }

        // find [l, r] such that tin[s] <= tin[i] <= tout[s]
        int lower = 0, upper = n - 1;
        while (lower < upper) {
            int mid = (lower + upper) / 2;
            if (nodes[s].tin <= nodes[order[mid]].tin) {
                upper = mid;
            }
            else {
                lower = mid + 1;
            }
        }

        int l = lower;

        lower = 0, upper = n - 1;
        while (lower < upper) {
            int mid = (lower + upper + 1) / 2;
            if (nodes[s].tout >= nodes[order[mid]].tin) {
                lower = mid;
            }
            else {
                upper = mid - 1;
            }
        }

        return {l, lower};
    }
};

std::vector<int> check_validity(int n, std::vector<int> x, std::vector<int> y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    int m = x.size(), q = S.size();
    DSUTree maxTree(n), minTree(n);
    for (int i = 1; i <= m; i++) {
        int u = x[i - 1], v = y[i - 1];
        u++; v++;
        maxTree.addEdge(u, v, -min(u, v)); // >= l
        minTree.addEdge(u, v, max(u, v)); // <= r
    }

    minTree.construct();
    maxTree.construct();

    vector<int> a = minTree.order;
    vector<int> b = maxTree.order;
    vector<int> pos(n + 1), c(n + 1);

    // for (auto i: a) cout << i << " ";
    // cout << endl;
    // for (auto i: b) cout << i << " ";
    // cout << endl;

    for (int i = 0; i < n; i++) {
        pos[a[i]] = i + 1;
    }
    for (int i = 0; i < n; i++) {
        c[i + 1] = pos[b[i]];
    }

    vector<int> ret;
    for (int i = 0; i < q; i++) {
        int s = S[i], e = E[i], l = L[i], r = R[i];
        // cin >> s >> e >> l >> r;
        s++; e++; l++; r++;
        auto [l1, r1] = minTree.getInterval(e, r);
        auto [l2, r2] = maxTree.getInterval(s, -l);

        // cout << l1 << " " << r1 << " " << l2 << " " << r2 << endl;
        vector<int> vs(n + 1);
        for (int i = l1; i <= r1; i++) {
            vs[a[i]]++;
        }
        int res = 0;
        for (int i = l2; i <= r2; i++) {
            if (vs[b[i]]) res = 1;
        }
        // cout << res << '\n';
        ret.push_back(res);
    }

    return ret;
}

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

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:179:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  179 |         auto [l1, r1] = minTree.getInterval(e, r);
      |              ^
werewolf.cpp:180:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  180 |         auto [l2, r2] = maxTree.getInterval(s, -l);
      |              ^

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51