#396786 (C++17) No.922 東北きりきざむたん

提出ソース
結果

問題	No.922 東北きりきざむたん
ユーザー	EgorKulikov
提出日時	2019-11-08 22:59:31
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	26,814 bytes
コンパイル時間	3,696 ms
コンパイル使用メモリ	242,972 KB
実行使用メモリ	47,968 KB
最終ジャッジ日時	2023-10-13 04:35:07
合計ジャッジ時間	15,216 ms
ジャッジサーバーID （参考情報）	judge14 / judge13
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	RE	-
testcase_01	RE	-
testcase_02	AC	2 ms 4,368 KB
testcase_03	RE	-
testcase_04	RE	-
testcase_05	RE	-
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	RE	-
testcase_12	RE	-
testcase_13	RE	-
testcase_14	RE	-
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	RE	-
testcase_19	RE	-
testcase_20	RE	-
testcase_21	RE	-
testcase_22	RE	-
testcase_23	RE	-
testcase_24	RE	-
testcase_25	RE	-
testcase_26	RE	-
testcase_27	RE	-
testcase_28	AC	98 ms 47,968 KB
testcase_29	RE	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Egor Kulikov
 */

#include <iostream>
#include <fstream>

#ifndef JHELPER_EXAMPLE_PROJECT_INPUT_H
#define JHELPER_EXAMPLE_PROJECT_INPUT_H

//
// Created by egor on 30.10.2019.
//

#ifndef JHELPER_EXAMPLE_PROJECT_GENERAL_H
#define JHELPER_EXAMPLE_PROJECT_GENERAL_H

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

const int MAX_INT = 2147483647;

const double PI = atan(1) * 4;

const int DX_KNIGHT[] = {2, 1, -1, -2, -2, -1, 1, 2};
const int DY_KNIGHT[] = {1, 2, 2, 1, -1, -2, -2, -1};
const int DX4[] = {1, 0, -1, 0};
const int DY4[] = {0, 1, 0, -1};

bool isValidCell(int x, int y, int rows, int cols) {
    return x >= 0 && y >= 0 && x < rows && y < cols;
}

void decreaseByOne() {
}

template <typename T, class...Vargs>
void decreaseByOne(vector<T>& arr, Vargs&...arrs) {
    for (int& i : arr) {
        i--;
    }
    decreaseByOne(arrs...);
}

template <typename T>
T minim(T& was, T cand) {
    return was = min(was, cand);
}

template <typename T>
T maxim(T& was, T cand) {
    return was = max(was, cand);
}

inline int bitCount(int number) {
    return __builtin_popcount(number);
}

inline int bitCount(ll number) {
    return __builtin_popcount(number);
}

#endif //JHELPER_EXAMPLE_PROJECT_GENERAL_H


class Input {
public:
    enum ErrorType {
        OK,
        END_OF_FILE,
        UNEXPECTED_SYMBOL,
        INVALID_CALL
    };

private:
    istream& in;
    bool exhausted = false;
    ErrorType error = OK;
    int get();
    template<typename T> T readInteger();
    int skipWhitespace();

public:
    Input(istream& in);
    int readInt();
    ll readLong();
    string readString();
    vector<int> readIntArray(int size);
    template<typename T> T readType();
    template<typename T, typename U> pair<T, U> readType();
    template<typename T> vector<T> readArray(int size);
    template<typename T1, typename T2> tuple<vector<T1>, vector<T2> > readArrays(int size);
    template<typename T1, typename T2, typename T3> tuple<vector<T1>, vector<T2>, vector<T3> > readArrays(int size);
    template<typename T1, typename T2, typename T3, typename T4>
        tuple<vector<T1>, vector<T2>, vector<T3>, vector<T4> > readArrays(int size);
    template<typename T1, typename T2, typename T3, typename T4, typename T5>
        tuple<vector<T1>, vector<T2>, vector<T3>, vector<T4>, vector<T5> > readArrays(int size);
    template<typename T> vector<vector<T> > readTable(int rows, int cols);

    string readLine();
};

inline bool isWhitespace(int c) {
    return isspace(c) || c == EOF;
}

int Input::skipWhitespace() {
    int c;
    do {
        c = get();
        if (exhausted) {
            error = END_OF_FILE;
            return c;
        }
    } while (isWhitespace(c));
    return c;
}

Input::Input(std::istream &in) : in(in) {
}

inline int Input::get() {
    int result = in.get();
    if (result == EOF) {
        exhausted = true;
    }
    return result;
}

template<typename T>
T Input::readType() {
    error = INVALID_CALL;
    return nullptr;
}

template<typename T>
T Input::readInteger() {
    error = OK;
    int c = skipWhitespace();
    if (error != OK) {
        return 0;
    }
    int sgn = 1;
    if (c == '-') {
        sgn = -1;
        c = get();
    }
    T res = 0;
    do {
        if (!isdigit(c)) {
            error = UNEXPECTED_SYMBOL;
            return 0;
        }
        res *= 10;
        res += c - '0';
        c = get();
    } while (!isWhitespace(c));
    return res * sgn;
}

template<>
int Input::readType() {
    return readInteger<int>();
}

template<>
ll Input::readType() {
    return readInteger<ll>();
}

template<>
char Input::readType() {
    error = OK;
    int c = skipWhitespace();
    if (error != OK) {
        return 0;
    }
    return c;
}

template<>
string Input::readType() {
    error = OK;
    int c = skipWhitespace();
    if (error != OK) {
        return "";
    }
    vector<char> res;
    do {
        if (error != OK) {
            return "";
        }
        res.push_back(c);
    } while (!isWhitespace(c = get()));
    return string(res.begin(), res.end());
}

inline int Input::readInt() {
    return readType<int>();
}

inline ll Input::readLong() {
    return readType<ll>();
}

template<typename T>
vector<T> Input::readArray(int size) {
    vector<T> res;
    res.reserve(size);
    for (int i = 0; i < size; i++) {
        res.push_back(readType<T>());
        if (error != OK) {
            res.clear();
            return res;
        }
    }
    return res;
}

vector<int> Input::readIntArray(int size) {
    return readArray<int>(size);
}

template<typename T1, typename T2>
tuple<vector<T1>, vector<T2> > Input::readArrays(int size) {
    vector<T1> v1;
    vector<T2> v2;
    v1.reserve(size);
    v2.reserve(size);
    for (int i = 0; i < size; ++i) {
        v1.push_back(readType<T1>());
        v2.push_back(readType<T2>());
    }
    return make_tuple(v1, v2);
}

string Input::readString() {
    return readType<string>();
}

template<typename T>
vector<vector<T>> Input::readTable(int rows, int cols) {
    vector<vector<T> > result;
    result.reserve(rows);
    for (int i = 0; i < rows; ++i) {
        result.push_back(readArray<T>(cols));
    }
    return result;
}

string Input::readLine() {
    error = OK;
    int c = skipWhitespace();
    if (error != OK) {
        return "";
    }
    int length = 0;
    vector<char> res;
    do {
        if (error != OK) {
            return "";
        }
        res.push_back(c);
        if (!isWhitespace(c)) {
            length = res.size();
        }
        c = get();
    } while (c != '\n' && c != '\r' && c != EOF);
    return string(res.begin(), res.begin() + length);
}

template<typename T1, typename T2, typename T3>
tuple<vector<T1>, vector<T2>, vector<T3> > Input::readArrays(int size) {
    vector<T1> v1;
    vector<T2> v2;
    vector<T3> v3;
    v1.reserve(size);
    v2.reserve(size);
    v3.reserve(size);
    for (int i = 0; i < size; ++i) {
        v1.push_back(readType<T1>());
        v2.push_back(readType<T2>());
        v3.push_back(readType<T3>());
    }
    return make_tuple(v1, v2, v3);
}

template<typename T1, typename T2, typename T3, typename T4>
tuple<vector<T1>, vector<T2>, vector<T3>, vector<T4> > Input::readArrays(int size) {
    vector<T1> v1;
    vector<T2> v2;
    vector<T3> v3;
    vector<T4> v4;
    v1.reserve(size);
    v2.reserve(size);
    v3.reserve(size);
    v4.reserve(size);
    for (int i = 0; i < size; ++i) {
        v1.push_back(readType<T1>());
        v2.push_back(readType<T2>());
        v3.push_back(readType<T3>());
        v4.push_back(readType<T4>());
    }
    return make_tuple(v1, v2, v3, v4);
}

template<typename T1, typename T2, typename T3, typename T4, typename T5>
tuple<vector<T1>, vector<T2>, vector<T3>, vector<T4>, vector<T5> > Input::readArrays(int size) {
    vector<T1> v1;
    vector<T2> v2;
    vector<T3> v3;
    vector<T4> v4;
    vector<T5> v5;
    v1.reserve(size);
    v2.reserve(size);
    v3.reserve(size);
    v4.reserve(size);
    v5.reserve(size);
    for (int i = 0; i < size; ++i) {
        v1.push_back(readType<T1>());
        v2.push_back(readType<T2>());
        v3.push_back(readType<T3>());
        v4.push_back(readType<T4>());
        v5.push_back(readType<T5>());
    }
    return make_tuple(v1, v2, v3, v4, v5);
}

#endif //JHELPER_EXAMPLE_PROJECT_INPUT_H

//
// Created by egor on 31.10.2019.
//

#ifndef JHELPER_EXAMPLE_PROJECT_OUTPUT_H
#define JHELPER_EXAMPLE_PROJECT_OUTPUT_H



class Output {
private:
    ostream& out;
    template<typename T> void printSingle(const T& value);
    template<typename T> void printSingle(const vector<T>& value);
    template<typename T, typename U> void printSingle(const pair<T, U>& value);

public:
    Output(ostream& out);
    void print();
    template<typename T, typename...Targs>void print(const T& first, const Targs... args);
    template<typename...Targs>void printLine(const Targs... args);
    void flush();
};

Output::Output(ostream &out) : out(out) {
    out << setprecision(12);
}

void Output::print() {
}

template<typename T, typename... Targs>
void Output::print(const T& first, const Targs... args) {
    printSingle(first);
    if (sizeof...(args) != 0) {
        out << ' ';
        print(args...);
    }
}

template<typename T>
void Output::printSingle(const T& value) {
    out << value;
}

template<typename... Targs>
void Output::printLine(const Targs... args) {
    print(args...);
    out << '\n';
}

void Output::flush() {
    out.flush();
}

template<typename T>
void Output::printSingle(const vector<T>& array) {
    unsigned int size = array.size();
    for (int i = 0; i < size; ++i) {
        out << array[i];
        if (i + 1 != size) {
            out << ' ';
        }
    }
}

template<typename T, typename U>
void Output::printSingle(const pair<T, U>& value) {
    out << value.first << ' ' << value.second;
}

#endif //JHELPER_EXAMPLE_PROJECT_OUTPUT_H

//
// Created by egor on 31.10.2019.
//

#ifndef JHELPER_EXAMPLE_PROJECT_DSU_H
#define JHELPER_EXAMPLE_PROJECT_DSU_H


//
// Created by egor on 31.10.2019.
//

#ifndef JHELPER_EXAMPLE_PROJECT_ALGO_H
#define JHELPER_EXAMPLE_PROJECT_ALGO_H



template <typename T>
inline void unique(vector<T>& v) {
    v.resize(unique(all(v)) - v.begin());
}

vi createOrder(int n) {
    vi order(n);
    for (int i = 0; i < n; i++) {
        order[i] = i;
    }
    return order;
}

template <typename T>
inline vector<vector<T> > makeArray(int a, int b) {
    return vector<vector<T> >(a, vector<T>(b));
}

//template <typename T>
//inline vector<vector<vector<T> > > makeArray(int a, int b, int c) {
//    return vector<vector<vector<T> > >(a, makeArray<T>(b, c));
//}

template <typename T>
inline vector<vector<T> > makeArray(int a, int b, T init) {
    return vector<vector<T> >(a, vector<T>(b, init));
}

template <typename T>
inline vector<vector<vector<T> > > makeArray(int a, int b, int c, T init) {
    return vector<vector<vector<T> > >(a, makeArray<T>(b, c, init));
}

template <typename T>
inline void addAll(vector<T>& v, const vector<T>& toAdd) {
    v.insert(v.end(), toAdd.begin(), toAdd.end());
}

#endif //JHELPER_EXAMPLE_PROJECT_ALGO_H


class DSU {
private:
    vi id;
    vi size;
    int setCount;

public:
    DSU(int n);
    int get(int i);
    int getSize(int i) { return size[get(i)]; }
    int getSetCount() { return setCount; }
    bool join(int a, int b);
};

DSU::DSU(int n) {
    id = createOrder(n);
    size = vi(n, 1);
    setCount = n;
}

int DSU::get(int i) {
    if (id[i] == i) {
        return i;
    }
    return id[i] = get(id[i]);
}

bool DSU::join(int a, int b) {
    a = get(a);
    b = get(b);
    if (a == b) {
        return false;
    }
    size[a] += size[b];
    size[b] = 0;
    id[b] = a;
    setCount--;
    return true;
}

#endif //JHELPER_EXAMPLE_PROJECT_DSU_H

//
// Created by egor on 04.11.2019.
//

#ifndef JHELPER_EXAMPLE_PROJECT_GRAPH_H
#define JHELPER_EXAMPLE_PROJECT_GRAPH_H



template <typename W, typename C>
class WeightedFlowEdge {
private:
    WeightedFlowEdge<W, C>* reverseEdge;

public:
    const int from;
    const int to;
    W weight;
    C capacity;
    int id;

    WeightedFlowEdge(int from, int to, W weight, C capacity) : from(from), to(to), weight(weight), capacity(capacity) {
        reverseEdge = new WeightedFlowEdge(this);
    }

    WeightedFlowEdge<W, C>* transposed() { return nullptr; }
    WeightedFlowEdge<W, C>* reverse() { return reverseEdge; }
    void push(C flow) {
        capacity -= flow;
        reverseEdge->capacity += flow;
    }
    C flow() const {
        return reverseEdge->capacity;
    }

private:
    WeightedFlowEdge(WeightedFlowEdge<W, C>* reverse) : from(reverse->to), to(reverse->from), weight(-reverse->weight), capacity(0) {
        reverseEdge = reverse;
    }
};

template <typename C>
class FlowEdge {
private:
    FlowEdge<C>* reverseEdge;

public:
    const int from;
    const int to;
    C capacity;
    int id;

    FlowEdge(int from, int to, C capacity) : from(from), to(to), capacity(capacity) {
        reverseEdge = new FlowEdge(this);
    }

    FlowEdge<C>* transposed() { return nullptr; }
    FlowEdge<C>* reverse() { return reverseEdge; }
    void push(C flow) {
        capacity -= flow;
        reverseEdge->capacity += flow;
    }
    C flow() const {
        return reverseEdge->capacity;
    }

private:
    FlowEdge(FlowEdge<C>* reverse) : from(reverse->to), to(reverse->from), capacity(0) {
        reverseEdge = reverse;
    }
};

template <typename W>
class WeightedEdge {
public:
    const int from;
    const int to;
    W weight;
    int id;

    WeightedEdge(int from, int to, W weight) : from(from), to(to), weight(weight) {
    }

    WeightedEdge<W>* transposed() { return nullptr; }
    WeightedEdge<W>* reverse() { return nullptr; }
};

template <typename W>
class BidirectionalWeightedEdge {
private:
    BidirectionalWeightedEdge<W>* transposedEdge;

public:
    const int from;
    const int to;
    W weight;
    int id;

    BidirectionalWeightedEdge(int from, int to, W weight) : from(from), to(to), weight(weight) {
        transposedEdge = new BidirectionalWeightedEdge(this);
    }

    BidirectionalWeightedEdge<W>* transposed() { return transposedEdge; }
    BidirectionalWeightedEdge<W>* reverse() { return nullptr; }

private:
    BidirectionalWeightedEdge(BidirectionalWeightedEdge<W>* transposed) : from(transposed->to), to(transposed->from), weight(transposed->weight) {
        transposedEdge = transposed;
    }
};

class SimpleEdge {
public:
    const int from;
    const int to;
    int id;

    SimpleEdge(int from, int to) : from(from), to(to) {
    }

    SimpleEdge* transposed() { return nullptr; }
    SimpleEdge* reverse() { return nullptr; }
};

class BidirectionalEdge {
private:
    BidirectionalEdge* transposedEdge;

public:
    const int from;
    const int to;
    int id;

    BidirectionalEdge(int from, int to) : from(from), to(to) {
        transposedEdge = new BidirectionalEdge(this);
    }

    BidirectionalEdge* transposed() { return transposedEdge; }
    BidirectionalEdge* reverse() { return nullptr; }

private:
    BidirectionalEdge(BidirectionalEdge* transposed) : from(transposed->to), to(transposed->from) {
        transposedEdge = transposed;
    }
};

template <class Edge>
class Graph {
public:
    int vertexCount;
    int edgeCount = 0;
    vector<vector<Edge*> > edges;

    Graph(int vertexCount) : vertexCount(vertexCount) {
        edges.resize(vertexCount);
    }

    void addEdge(Edge* edge) {
        edge->id = edgeCount;
        edges[edge->from].push_back(edge);
        if (edge->reverse() != nullptr) {
            edge->reverse()->id = edgeCount;
            edges[edge->reverse()->from].push_back(edge->reverse());
        }
        if (edge->transposed() != nullptr) {
            edges[edge->transposed()->from].push_back(edge->transposed());
            edge->transposed()->id = edgeCount;
            if (edge->transposed()->reverse() != nullptr) {
                edges[edge->transposed()->reverse()->from].push_back(edge->transposed()->reverse());
                edge->transposed()->reverse()->id = edgeCount;
            }
        }
        edgeCount++;
    }
};

typedef FlowEdge<ll> LongFlowEdge;
typedef WeightedEdge<ll> LongWeightedEdge;
typedef FlowEdge<int> IntFlowEdge;
typedef WeightedEdge<int> IntWeightedEdge;
typedef BidirectionalWeightedEdge<ll> LongBiWeightedEdge;
typedef BidirectionalWeightedEdge<int> IntBiWeightedEdge;

#endif //JHELPER_EXAMPLE_PROJECT_GRAPH_H

#ifndef CPP_LCA_H
#define CPP_LCA_H


//
// Created by kulikov on 11/7/2019.
//

#include <functional>

#ifndef JHELPER_EXAMPLE_PROJECT_INTERVAL_TREE_H
#define JHELPER_EXAMPLE_PROJECT_INTERVAL_TREE_H



template<typename Value, typename Delta, Value defaultValue = 0, Delta defaultDelta = 0>
class IntervalTree {
private:
    const int size;
    const function<Value(Value, Value)> &joinValue;
    const function<Delta(Delta, Delta)> &joinDelta;
    const function<Value(Value, Delta, int, int)> &accumulate;
    const function<Value(int)> &initValue;
    vector<Value> value;
    vector<Delta> delta;

    void init(int root, int left, int right) {
        if (left + 1 == right) {
            value[root] = initValue(left);
        } else {
            int mid = (left + right) >> 1;
            init(2 * root + 1, left, mid);
            init(2 * root + 2, mid, right);
            value[root] = joinValue(value[2 * root + 1], value[2 * root + 2]);
        }
    }

    void apply(int root, Delta dlt, int left, int right) {
        value[root] = accumulate(value[root], dlt, left, right);
        delta[root] = joinDelta(delta[root], dlt);
    }

    void pushDown(int root, int left, int mid, int right) {
        apply(2 * root + 1, delta[root], left, mid);
        apply(2 * root + 2, delta[root], mid, right);
        delta[root] = defaultDelta;
    }

    void update(int root, int left, int right, int from, int to, Delta dlt) {
        if (left >= from && right <= to) {
            apply(root, dlt, left, right);
            return;
        }
        if (right <= from || left >= to) {
            return;
        }
        int mid = (left + right) >> 1;
        pushDown(root, left, mid, right);
        update(2 * root + 1, left, mid, from, to, dlt);
        update(2 * root + 2, mid, right, from, to, dlt);
    }

    Value query(int root, int left, int right, int from, int to) {
        if (left >= from && right <= to) {
            return value[root];
        }
        if (right <= from || left >= to) {
            return defaultValue;
        }
        int mid = (left + right) >> 1;
        pushDown(root, left, mid, right);
        return joinValue(query(2 * root + 1, left, mid, from, to), query(2 * root + 2, mid, right, from, to));
    }

public:
    IntervalTree(int size, const function<Value(Value, Value)> &joinValue,
                 const function<Delta(Delta, Delta)> &joinDelta,
                 function<Value(Value, Delta, int, int)> &accumulate,
                 const function<Value(int)> &initValue = [](int at) -> Value { return defaultValue; }) :
            size(size), joinValue(joinValue), joinDelta(joinDelta), accumulate(accumulate), initValue(initValue) {
        int vertexSize = size * 4;
        value = vector<Value>(vertexSize);
        delta = vector<Delta>(vertexSize, defaultDelta);
        init(0, 0, size);
    }

    void update(int from, int to, Delta delta) {
        update(0, 0, size, from, to, delta);
    }

    Value query(int from, int to) {
        return query(0, 0, size, from, to);
    }
};

template <typename Value, Value defaultValue = 0>
class ReadOnlyIntervalTree {
private:
    const int size;
    const function<Value(Value, Value)> &joinValue;
    vector<Value> value;

    void init(int root, int left, int right, const vector<Value>& array) {
        if (left + 1 == right) {
            value[root] = array[left];
        } else {
            int mid = (left + right) >> 1;
            init(2 * root + 1, left, mid, array);
            init(2 * root + 2, mid, right, array);
            value[root] = joinValue(value[2 * root + 1], value[2 * root + 2]);
        }
    }

    Value query(int root, int left, int right, int from, int to) {
        if (left >= from && right <= to) {
            return value[root];
        }
        if (right <= from || left >= to) {
            return defaultValue;
        }
        int mid = (left + right) >> 1;
        return joinValue(query(2 * root + 1, left, mid, from, to), query(2 * root + 2, mid, right, from, to));
    }

public:
    ReadOnlyIntervalTree(const vector<Value>& array, const function<Value(Value, Value)> &joinValue) :
            size(array.size()), joinValue(joinValue) {
        int vertexSize = size * 4;
        value = vector<Value>(vertexSize);
        init(0, 0, size, array);
    }

    Value query(int from, int to) {
        return query(0, 0, size, from, to);
    }
};


#endif //JHELPER_EXAMPLE_PROJECT_INTERVAL_TREE_H



template <class Edge>
class LCA {
private:
    vi order;
    vi position;
    Graph<Edge>* graph;
    ReadOnlyIntervalTree<int, -1>* lcaTree;
    vi level;

public:
    LCA(Graph<Edge>* graph, int root = 0) : graph(graph) {
        int vertexCount = graph->vertexCount;
        order = vi(2 * vertexCount - 1);
        position = vi(vertexCount, -1);
        level = vi(vertexCount);
        vi index = vi(vertexCount);
        vi last = vi(vertexCount);
        vi stack = vi(vertexCount);
        stack[0] = root;
        int size = 1;
        int j = 0;
        last[root] = -1;
        while (size > 0) {
            int vertex = stack[--size];
            if (position[vertex] == -1) {
                position[vertex] = j;
            }
            order[j++] = vertex;
            if (last[vertex] != -1) {
                level[vertex] = level[last[vertex]] + 1;
            }
            while (index[vertex] < graph->edges[vertex].size() && last[vertex] == graph->edges[vertex][index[vertex]]->to) {
                index[vertex]++;
            }
            if (index[vertex] < graph->edges[vertex].size()) {
                stack[size++] = vertex;
                int to = graph->edges[vertex][index[vertex]]->to;
                stack[size++] = graph->edges[vertex][index[vertex]]->to;
                last[to] = vertex;
                index[vertex]++;
            }
        }
        lcaTree = new ReadOnlyIntervalTree<int, -1>(order, [this](int left, int right) -> int {
            if (left == -1) {
                return right;
            }
            if (right == -1) {
                return left;
            }
            if (level[left] < level[right]) {
                return left;
            }
            return right;
        });
    }

    int getPosition(int vertex) { return position[vertex]; }
    int getLCA(int first, int second) {
        return lcaTree->query(min(position[first], position[second]), max(position[first], position[second]) + 1);
    }
    int getLevel(int vertex) {
        return level[vertex];
    }
    int getPathLength(int first, int second) {
        return level[first] + level[second] - 2 * level[getLCA(first, second)];
    }
};

#endif //CPP_LCA_H


class c {
    int fillDown(int vertex, int last, Graph<BidirectionalEdge>& graph, vi& qty, vi& part, vi& down) {
        down[vertex] = qty[part[vertex]];
        for (auto edge : graph.edges[vertex]) {
            if (edge->to != last) {
                down[vertex] += fillDown(edge->to, vertex, graph, qty, part, down);
            }
        }
        return down[vertex];
    }

    int getOptimal(int vertex, int last, Graph<BidirectionalEdge>& graph, vi& down, int all) {
        for (auto edge : graph.edges[vertex]) {
            if (edge->to != last && down[edge->to] * 2 > all) {
                return getOptimal(edge->to, vertex, graph, down, all);
            }
        }
        return vertex;
    }

public:
	void solve(istream& inp, ostream& outp) {
        Input in(inp);
        Output out(outp);

        int n = in.readInt();
        int m = in.readInt();
        int q = in.readInt();

        vi u, v, a, b;
        tie(u, v) = in.readArrays<int, int>(m);
        tie(a, b) = in.readArrays<int, int>(q);

        decreaseByOne(u, v, a, b);

        DSU dsu(n);
        for (int i = 0; i < m; ++i) {
            dsu.join(u[i], v[i]);
        }

        int setCount = dsu.getSetCount();
        vi heads;
        for (int i = 0; i < n; i++) {
            if (dsu.get(i) == i) {
                heads.push_back(i);
            }
        }

        vi did(n);
        for (int i = 0; i < n; i++) {
            did[i] = lower_bound(all(heads), dsu.get(i)) - heads.begin();
        }

        vector<vi> parts(setCount);
        for (int i = 0; i < n; i++) {
            parts[did[i]].push_back(i);
        }

        vi size(setCount);
        for (int i = 0; i < n; i++) {
            size[did[i]]++;
        }

        vector<Graph<BidirectionalEdge>*> graphs;
        graphs.reserve(setCount);
        for (int i = 0; i < setCount; i++) {
            graphs.push_back(new Graph<BidirectionalEdge>(size[i]));
        }

        vi convert(n);
        for (int i = 0; i < n; i++) {
            int id = did[i];
            convert[i] = lower_bound(all(parts[id]), i) - parts[id].begin();
        }

        for (int i = 0; i < m; i++) {
            int id = did[v[i]];
            graphs[id]->addEdge(new BidirectionalEdge(convert[v[i]], convert[u[i]]));
        }

        vector<LCA<BidirectionalEdge>*> lcas;
        for (int i = 0; i < setCount; i++) {
            lcas.push_back(new LCA<BidirectionalEdge>(graphs[i]));
        }

        ll answer = 0;
        vi qty(n);
        for (int i = 0; i < q; ++i) {
            if (did[a[i]] != did[b[i]]) {
                qty[a[i]]++;
                qty[b[i]]++;
            } else {
                answer += lcas[did[a[i]]]->getPathLength(convert[a[i]], convert[b[i]]);
            }
        }

        for (int i = 0; i < setCount; i++) {
            vi down(parts[i].size());
            fillDown(0, -1, *graphs[i], qty, parts[i], down);
            int optimal = getOptimal(0, -1, *graphs[i], down, down[0]);
            for (int j = 0; j < parts[i].size(); j++) {
                answer += lcas[i]->getPathLength(j, optimal) * ll(qty[parts[i][j]]);
            }
        }

        out.printLine(answer);
	}
};


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
	c solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}
yukicoder

結果

テストケース

ソースコード
