#1101832 (C++17) No.3193 Submit Your Solution

• 問題: No.3193 Submit Your Solution
• ユーザー: GOTKAKO
• 提出日時: 2025-06-28 04:41:00
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 9,728 bytes
• コンパイル時間: 3,957 ms
• コンパイル使用メモリ: 247,756 KB
• 実行使用メモリ: 181,508 KB
• 最終ジャッジ日時: 2025-06-28 04:41:54
• 合計ジャッジ時間: 50,590 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

ファイルパターン	結果
sample	WA * 2
other	WA * 17

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

template <typename T>
class SparseTable{
    private:
    T op(T a,T b){return min(a,b);} //条件op(A,A)=A &op(op(A,B),C)=op(A,op(B,C));
    T e(T a,T b){return {1001001001,-1};}
    array<int,400000> check;
    array<array<T,400000>,19> table;
    public:
    void make(const vector<T> &A){
        int n = A.size();
        int p2 = 1,l = 0;
        for(int i=1; i<400000; i++){
            if(i == p2) check[i] = l,l++,p2 *= 2;
            else check[i] = check[i-1];
        }
        for(int i=0; i<n; i++) table[0][i] = A[i];
        for(int i=n; i<400000; i++) table[0][i] = {1001001001,-1};
        l = 1;
        for(int i=2; i<=n; i*=2,l++){
            for(int k=0; k<=n-i; k++) table[l][k] = op(table[l-1][k],table[l-1][k+(i>>1)]);
            for(int k=n-i+1; k<400000; k++) table[l][k] = {1001001001,-1};
        }
    }
    T rangeans(int l,int r){//[L,R)だよ.
        int pos = check[r-l]; r -= 1<<pos;
        return op(table[pos][l],table[pos][r]);
    }
};
class LCA{
    private:
    SparseTable<pair<int,int>> ST;
    public:
    vector<int> in,out;
    vector<ull> dist;
    void make1(const vector<int> &P){// p0=-1でp1以降だけ
        int r = 0;
        vector<vector<int>> G(P.size()+1);
        for(int i=0; i<P.size(); i++) G.at(P.at(i)).push_back(i+1); 
        make3(G,r);
    }
    void make2(const vector<int> &P){//pi=-1 iは固定されていない.
        int r = -1;
        vector<vector<int>> G(P.size());
        for(int i=0; i<P.size(); i++){
            if(P.at(i) == -1) r = i;
            else G.at(P.at(i)).push_back(i);
        }
        make3(G,r);
    }
    void make3(const vector<vector<int>> &Graph,int root){ //直接グラフを渡す.
        int t = 0,dep = 0,n = Graph.size(),pos = root;
        dist.resize(n),in.resize(n),out.resize(n);
 
        vector<pair<int,int>> depth;
        vector<int> Itr(n,-1),P(n,-1);
        while(pos != -1){
            depth.push_back({dep,pos});
            if(++Itr.at(pos) == 0) in.at(pos) = t;
            int to = P.at(pos);
            if(Itr.at(pos) == Graph.at(pos).size()) out.at(pos) = ++t;
            else{
                to = Graph.at(pos).at(Itr.at(pos));
                if(to == P.at(pos)){
                    Itr.at(pos)++;
                    if(Itr.at(pos) == Graph.at(pos).size()) out.at(pos) = ++t;
                    else to = Graph.at(pos).at(Itr.at(pos));
                }
            }
            if(to != P.at(pos)) dist.at(to) = dist.at(pos)+1,P.at(to) = pos,t++,dep++;
            else dep--;
            pos = to;
        }
        ST.make(depth);
    }
    int lca(int u,int v){
        int tu = in.at(u),tv = in.at(v);
        if(tu > tv) swap(tu,tv);
        return ST.rangeans(tu,tv+1).second;
    }
    int twodist(int u,int v){return dist.at(u)+dist.at(v)-2*dist.at(lca(u,v));}
    int onedist(int u){return dist.at(u);} 
    pair<vector<int>,vector<int>> getinout(){return {in,out};}
};

LCA L;
int in[200000],out[200000];
vector<pair<int,int>> in2;
pair<vector<vector<int>>,vector<vector<vector<int>>>> AuxiliaryTree(const vector<int> &A,int maxa){
    //色ごとに木を構築するやつ O(NlogN) 定数悪い実装.
    //return {色ごとの実際の頂点番号,色ごとのTree}
    //重み付きだったら修正必須.
    int N = A.size();
    vector<vector<int>> ret1(maxa);
    for(auto [t,i] : in2) if(A.at(i) != -1) ret1.at(A.at(i)).emplace_back(i);

    for(auto &as : ret1){
        int n = as.size();
        for(int i=0; i<n-1; i++){
            int pos1 = as.at(i),pos2 = as.at(i+1);
            int pos3 = L.lca(pos1,pos2);
            assert(pos3 != -1);
            as.emplace_back(pos3);
        }
        sort(as.begin(),as.end(),[&](auto &a,auto &b){return in[a]<in[b];});
        as.erase(unique(as.begin(),as.end()),as.end());
    }

    vector<vector<vector<int>>> ret2(maxa);
    for(int i=0; i<maxa; i++){
        int siz = ret1.at(i).size();
        ret2.at(i).resize(siz);
        stack<pair<int,int>> st;
        for(int k=0; k<siz; k++){
            int pos = ret1.at(i).at(k),out1 = out[pos];
            while(st.size()){
                auto[bk,out2] = st.top();
                if(out1 < out2){
                    ret2.at(i).at(bk).emplace_back(k);
                    ret2.at(i).at(k).emplace_back(bk);
                    break;
                } 
                else st.pop();
            }
            st.push({k,out1});
        }
    }
    return{ret1,ret2};
}

tuple<ull,ull,ull,ull> V[200000];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; cin >> N;
    //if(N != 199910) return 0;
    vector<vector<int>> Graph(N),Graph2(N);
    for(int i=0; i<N-1; i++){
        int u = i,v = i+1;
        //cin >> u >> v,u--; v--;
        Graph.at(u).push_back(v);
        Graph.at(v).push_back(u);
    }
    for(int i=0; i<N-1; i++){
        int u = i,v = i+1;
        //cin >> u >> v,u--; v--;
        Graph2.at(u).push_back(v);
        Graph2.at(v).push_back(u);
    }

    L.make3(Graph2,0);
    for(int i=0; i<N; i++) in[i] = L.in.at(i),out[i] = L.out.at(i);
    in2.resize(N);
    for(int i=0; i<N; i++) in2.at(i) = {in[i],i};
    sort(in2.begin(),in2.end());

    ull answer = 0;
    vector<bool> stop(N);    
    auto findsiz = [&](auto self,int pos,int back) -> int {
        if(stop.at(pos)) return 0;
        int ret = 1;
        for(auto to : Graph.at(pos)) if(to != back) ret += self(self,to,pos);
        return ret;
    };
    auto centroid = [&](auto self,int pos,int back,int siz) -> pair<int,int> {
        if(stop.at(pos)) return {0,-1};
        int ret = 1;
        int cent = -1;
        bool ok = true;
        for(auto to : Graph.at(pos)){
            if(to == back) continue;
            auto [v,c] = self(self,to,pos,siz);
            if(v > siz/2) ok = false;
            if(c != -1) cent = c;
            ret += v; 
        }
        if(siz-ret > siz/2) ok = false;
        if(ok) cent = pos;
        return {ret,cent};
    };
    vector<int> Ps = {0};
    vector<ull> dist2 = L.dist;

    while(Ps.size()){
        for(auto &p : Ps){
            int siz = findsiz(findsiz,p,-1);
            p = centroid(centroid,p,-1,siz).second;
        }

        vector<int> C1(N,-1),C2(N,-1);
        int cpos1 = 0,cpos2 = 0;
        
        for(auto &p : Ps){
            auto dfs = [&](auto dfs,int pos,int back,ull dep) -> void {
                if(stop.at(pos)) return;
                C1.at(pos) = cpos1,C2.at(pos) = cpos2;
                for(auto to : Graph.at(pos)) if(to != back) dfs(dfs,to,pos,dep+1);
            };
            for(auto to : Graph.at(p)) if(stop.at(to) == false) dfs(dfs,to,p,1),cpos2++;
            C1.at(p) = cpos1++;
        }
        
        auto[B1,G1] = AuxiliaryTree(C1,cpos1);
        auto[B2,G2] = AuxiliaryTree(C2,cpos2);
        ///*
        int idx = 0;
        for(auto &G : G1){
            if(idx >= Ps.size()) break;
            int root = Ps.at(idx);
            {
                auto dfs = [&](auto dfs,int pos,int back,ull dep) -> void {
                    if(stop.at(pos)) return;
                    V[pos] = {1,dep,dist2.at(pos),dep*dist2.at(pos)};
                    for(auto to : Graph.at(pos)) if(to != back) dfs(dfs,to,pos,dep+1);
                };  
                dfs(dfs,root,-1,0);
            }
            {
                auto dfs = [&](auto dfs,int pos,int back) -> tuple<ull,ull,ull,ull> {
                    int p = B1.at(idx).at(pos);
                    auto [c,d,e,s] = V[p]; V[p] = {0,0,0,0};
                    ull di = dist2.at(p)*2;
                    for(auto to : G.at(pos)){
                        if(to == back) continue;
                        auto [c2,d2,e2,s2] = dfs(dfs,to,pos);
                        answer -= di*(d*c2+d2*c);
                        answer += d*e2+e*d2;
                        answer += s*c2+s2*c;
                        c += c2,d += d2,e += e2,s += s2;
                    }
                    return {c,d,e,s};
                };
                dfs(dfs,0,-1);
            }
            idx++;
        }
        cpos2 = 0;
        for(auto p : Ps) for(auto root : Graph.at(p)) if(stop.at(root) == false){
            auto &G = G2.at(cpos2);
            auto &B = B2.at(cpos2);
            {
                auto dfs = [&](auto dfs,int pos,int back,ull dep) -> void {
                    if(stop.at(pos)) return;
                    V[pos] = {1,dep,dist2.at(pos),dep*dist2.at(pos)};
                    for(auto to : Graph.at(pos)) if(to != back) dfs(dfs,to,pos,dep+1);
                };  
                dfs(dfs,root,p,1);
            }
            {
                auto dfs = [&](auto dfs,int pos,int back) -> tuple<ull,ull,ull,ull> {
                    int p = B.at(pos);
                    auto [c,d,e,s] = V[p]; V[p] = {0,0,0,0};
                    ull di = dist2.at(p)*2;
                    for(auto to : G.at(pos)){
                        if(to == back) continue;
                        auto [c2,d2,e2,s2] = dfs(dfs,to,pos);
                        answer += di*(d*c2+d2*c);
                        answer -= d*e2+e*d2;
                        answer -= s*c2+s2*c;
                        c += c2,d += d2,e += e2,s += s2;
                    }
                    return {c,d,e,s};
                };
                dfs(dfs,0,-1);
            }
            cpos2++;
        }
        //*/

        vector<int> next;
        for(auto &p : Ps){
            for(auto to : Graph.at(p)) if(!stop.at(to)) next.push_back(to);
            stop.at(p) = true;
        }
        swap(Ps,next);
    }
    answer *= 2;
    //answer = 77714187941852070; //さいあく
    cout << answer << endl;
}