Submission #1768409


Source Code Expand

#include <bits/stdc++.h>
#define rep(i, n) for (lli i = 0; i < (n); i++)
#define rrep(i, n) for (lli i = (n)-1; i >= 0; i--)
using namespace std;
using lli = long long int;
template <class T>
class segtree
{
public:
    lli n;
    vector<T> dat;
    function<T(T, T)> func;
    T dummy;
    segtree<T>(lli _n, function<T(T, T)> f, T dummy) : func(f), dummy(dummy)
    {
        n = 1;
        while (n < _n) {
            n = n * 2;
        }
        dat.assign(2 * n - 1, dummy);
    }
    void update(lli k, T a)
    {
        k += n - 1;
        dat[k] = a;
        while (k > 0) {
            k = (k - 1) / 2;
            dat[k] = func(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }
    T query(int a, int b)
    {
        return query(a, b, 0, 0, n);
    }
    // [a,b)の何かを求める.
    T query(int a, int b, int k, int l, int r)
    {
        //交差しないときはダミー
        if (r <= a || b <= l)
            return dummy;
        if (a <= l && r <= b)
            return dat[k];
        else {
            T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
            T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
            return func(vl, vr);
        }
    }
    T get(int a)
    {
        return query(a, a + 1, 0, 0, n);
    }
};

template <class T>
struct hldec {
    int n;
    int col = 0;
    vector<vector<int>> e;
    vector<vector<int>> heavy;
    vector<vector<int>> light;
    vector<vector<T>> cls;
    vector<T> vers;
    vector<pair<int, int>> pos;
    vector<pair<int, int>> par;
    function<T(T, T)> f;
    T unit;
    vector<segtree<T>> vec_seg;
    int root = 0;
    vector<int> size;
    hldec(int n, vector<T> vers, function<T(T, T)> f, T unit, int root = 0) : n(n), root(root), vers(vers), unit(unit), f(f)
    {
        e.assign(n, {});
        par.assign(n, make_pair(-1, -1));
        heavy.assign(n, {});
        light.assign(n, {});
        size.assign(n, 0);
        pos.assign(n, make_pair(-1, -1));
        cls.assign(n, {});
    }
    void add(int u, int v)
    {
        e[u].push_back(v);
        e[v].push_back(u);
    }
    int sub_tree_size(int cur, int par)
    {
        int tmp = 1;
        for (auto s : e[cur]) {
            if (par != s) {
                tmp += sub_tree_size(s, cur);
            }
        }
        size[cur] = tmp;
        return tmp;
    }
    void dfs_label(int cur, int par)
    {
        lli idx = -1;
        lli mem = 0;
        rep(i, e[cur].size())
        {
            auto s = e[cur][i];
            if (s != par) {
                if (size[s] > mem) {
                    mem = size[s];
                    idx = i;
                }
            }
        }
        if (idx == -1)
            return;
        rep(i, e[cur].size())
        {
            auto s = e[cur][i];
            if (s != par) {
                if (idx == i) {
                    heavy[cur].push_back(s);
                } else {
                    light[cur].push_back(s);
                }
                dfs_label(s, cur);
            }
        }
    }
    void edge_labeling()
    {
        sub_tree_size(root, -1);
        dfs_label(root, -1);
    }
    void dfs_arrays(int cur, int c)
    {
        cls[c].push_back(vers[cur]);
        int idx = cls[c].size() - 1;
        pos[cur] = make_pair(c, cls[c].size() - 1);
        for (auto s : light[cur]) {
            col++;
            par[col] = make_pair(c, idx);
            dfs_arrays(s, col);
        }
        for (auto s : heavy[cur]) {
            dfs_arrays(s, c);
        }
    }
    void make_arrays()
    {
        dfs_arrays(root, 0);
    }
    void build_segtree()
    {
        rep(j, cls.size())
        {
            auto& s = cls[j];
            int size = s.size();
            segtree<T> seg(size, f, unit);
            rep(i, size)
            {
                seg.update(i, s[i]);
            }
            vec_seg.push_back(seg);
        }
    }
    void build(bool opt = false)
    {
        edge_labeling();
        if (opt) {
            e.clear();
        }
        make_arrays();
        if (opt) {
            heavy.clear();
            light.clear();
        }

        build_segtree();
    }
    T query(int u, int v)
    {
        vector<pair<int, int>> hist_u;
        vector<pair<int, int>> hist_v;
        rep(j, 2)
        {
            int tmp = j == 1 ? u : v;
            while (true) {
                int cur_col = pos[tmp].first;
                if (j)
                    hist_u.push_back(pos[tmp]);
                else
                    hist_v.push_back(pos[tmp]);
                tmp = par[cur_col].second;
                if (tmp == -1)
                    break;
            }
        }
        int cnt = 0;
        T ans = unit;
        while (true) {
            int idx_u = hist_u.size() - cnt - 1;
            int idx_v = hist_v.size() - cnt - 1;
            if (hist_u[idx_u].first == hist_v[idx_v].first) {
                int r = max(hist_u[idx_u].second, hist_v[idx_v].second) + 1;
                int l = min(hist_u[idx_u].second, hist_v[idx_v].second);
                ans = f(vec_seg[hist_u[idx_u].first].query(l, r), ans);
                break;
            }
            cnt++;
        }
        rep(i, hist_u.size() - cnt - 1)
        {
            ans = f(vec_seg[hist_u[i].first].query(0, hist_u[i].second + 1), ans);
        }
        rep(i, hist_v.size() - cnt - 1)
        {
            ans = f(vec_seg[hist_v[i].first].query(0, hist_v[i].second + 1), ans);
        }
        return ans;
    }
};
vector<pair<lli, lli>> e[4005];
vector<pair<lli, lli>> ne[4005];
int main()
{
    int n, m;
    cin >> n >> m;
    int a, b;
    lli c;
    rep(i, m)
    {
        cin >> a >> b >> c;
        a--, b--;
        e[a].push_back(make_pair(b, c));
        e[b].push_back(make_pair(a, c));
    }
    using p = pair<lli, pair<lli, lli>>;
    priority_queue<p, vector<p>, greater<p>> que;
    bool used[4005] = {};
    que.push(make_pair(0, make_pair(0, -1)));
    lli ans = 0;
    int hoge = n;
    vector<pair<int, int>> edge;
    vector<lli> v(2 * n, 0);
    while (!que.empty()) {
        auto cur = que.top().second;
        auto cost = que.top().first;
        que.pop();
        if (used[cur.first])
            continue;
        used[cur.first] = true;
        ans += cost;
        if (cur.second != -1) {
            edge.push_back(make_pair(cur.first, hoge));
            edge.push_back(make_pair(cur.second, hoge));
            v[hoge] = cost;
            hoge++;
        }
        for (auto s : e[cur.first]) {
            que.push(make_pair(s.second, make_pair(s.first, cur.first)));
        }
    }


    auto f = [](lli u, lli v) -> lli { return max(u, v); };
    hldec<lli> tr(2 * n, v, f, 0);
    for(auto s:edge){
        tr.add(s.first,s.second);
    }
    // tr.add(0, 1);
    // tr.add(0, 2);
    // tr.add(1, 3);
    // tr.add(1, 4);
    tr.build(true);
    int s, t, q;
    cin >> q;
    rep(i, q)
    {
        cin >> s >> t;
        cout << ans -tr.query(s - 1, t - 1) << endl;
    }
    // //cout << tr.query(0,1)<<endl;
    // cout << tr.query(3, 4) << endl;
};
;

Submission Info

Submission Time
Task A - Graph
User uenoku
Language C++14 (GCC 5.4.1)
Score 0
Code Size 7367 Byte
Status RE
Exec Time 3114 ms
Memory 44396 KB

Judge Result

Set Name Sample subtask1 subtask2 All
Score / Max Score 0 / 0 0 / 200 0 / 300 0 / 200
Status
AC × 2
AC × 2
WA × 1
RE × 9
AC × 3
WA × 2
RE × 16
AC × 5
WA × 2
RE × 24
Set Name Test Cases
Sample sample_1.txt, sample_2.txt
subtask1 sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
subtask2 sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt
All sample_1.txt, sample_2.txt, sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt
Case Name Status Exec Time Memory
sample_1.txt AC 1 ms 384 KB
sample_2.txt AC 1 ms 384 KB
subtask_1_1.txt WA 2 ms 640 KB
subtask_1_10.txt RE 2572 ms -2066732 KB
subtask_1_11.txt AC 1 ms 384 KB
subtask_1_2.txt RE 2358 ms -2088492 KB
subtask_1_3.txt RE 2848 ms -2039596 KB
subtask_1_4.txt RE 2313 ms -2093536 KB
subtask_1_5.txt RE 2314 ms -2093668 KB
subtask_1_6.txt RE 2442 ms -2078000 KB
subtask_1_7.txt RE 2862 ms -2040748 KB
subtask_1_8.txt RE 2310 ms -2093152 KB
subtask_1_9.txt RE 2320 ms -2092432 KB
subtask_2_1.txt RE 3114 ms -2040492 KB
subtask_2_2.txt RE 2863 ms -2039344 KB
subtask_2_3.txt WA 563 ms 44396 KB
subtask_2_4.txt RE 2857 ms -2042664 KB
subtask_2_5.txt RE 2309 ms -2093796 KB
subtask_2_6.txt RE 2332 ms -2091812 KB
subtask_2_7.txt RE 2437 ms -2078000 KB
subtask_2_8.txt RE 2858 ms -2040236 KB
subtask_3_1.txt RE 2850 ms -2039216 KB
subtask_3_2.txt RE 2867 ms -2040232 KB
subtask_3_3.txt RE 2310 ms -2093924 KB
subtask_3_4.txt RE 2321 ms -2092816 KB
subtask_3_5.txt RE 2590 ms -2066996 KB
subtask_3_6.txt RE 2717 ms -2045228 KB
subtask_3_7.txt RE 2857 ms -2040748 KB
subtask_3_8.txt RE 2870 ms -2041132 KB