結果

問題 No.439 チワワのなる木
ユーザー ytft
提出日時 2021-03-26 07:04:39
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 136 ms / 5,000 ms
コード長 4,421 bytes
コンパイル時間 2,630 ms
コンパイル使用メモリ 192,076 KB
実行使用メモリ 32,680 KB
最終ジャッジ日時 2024-11-27 17:09:52
合計ジャッジ時間 3,994 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function 'std::vector<std::vector<int> > Graph<verticesValueType, edgesValueType>::getConnected() [with verticesValueType = int; edgesValueType = int]':
main.cpp:30:5: warning: control reaches end of non-void function [-Wreturn-type]
   30 |     }
      |     ^

ソースコード

diff # 

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

template<typename verticesValueType,typename edgesValueType>
class Graph{
public:
    vector<vector<int>> edges;
    vector<int> parent;
    int numberOfVertices;
    vector<vector<int>> adjacencyMatrix;
    vector<vector<int>> connected;
    vector<vector<int>> children;
    vector<verticesValueType> verticesValue;
    vector<edgesValueType> edgesValue;
    Graph(vector<vector<int>> e,int N){
        edges=e;
        numberOfVertices=N;
    }
    vector<vector<int>> getConnected(){
        if(connected.size()>0)return connected;
        if(edges.size()>0){
            connected.resize(numberOfVertices);
            connected.clear();
            for(int i=edges.size()-1;i>=0;i--){
                connected[edges[i][0]].push_back(edges[i][1]);
                connected[edges[i][1]].push_back(edges[i][0]);
            }
            return connected;
        }
    }
    vector<int> getParent(int root=0){
        if(parent.size()>0)return parent;
        parent.resize(numberOfVertices);
        vector<bool> isWritten(numberOfVertices);
        vector<vector<int>> c=getConnected();
        queue<vector<int>> q;
        q.push({-1,root});
        while(!q.empty()){
            if(isWritten[q.front()[1]]){
                goto end;
            }
            isWritten[q.front()[1]]=true;
            parent[q.front()[1]]=q.front()[0];
            for(int i:connected[q.front()[1]]){
                q.push({q.front()[1],i});
            }
            end:{}
            q.pop();
        }
        return parent;
    }
    vector<vector<int>> getChildren(int root=0){
        getParent(root);
        if(children.size()>0)return children;
        children.resize(numberOfVertices);
        children.clear();
        for(int i=0;i<numberOfVertices;i++){
            if(parent[i]>-1){
                children[parent[i]].push_back(i);
            }
        }
        return children;
    }
    vector<int> orderFromChildren(){
        getParent();
        getChildren();
        vector<int> ret(0);
        vector<int> count(numberOfVertices);
        queue<int> q;
        for(int i=0;i<numberOfVertices;i++){
            if(children[i].size()==0){
                q.push(i);
            }
        }
        while(true){
            ret.push_back(q.front());
            if(parent[q.front()]==-1){
                return ret;
            }
            count[parent[q.front()]]++;
            if(count[parent[q.front()]]==children[parent[q.front()]].size()){
                q.push(parent[q.front()]);
            }
            q.pop();
        }
        return ret;
    }
};
int main(){
    int N;
    string S;
    cin>>N>>S;
    vector<vector<int>> edges(0,vector<int>(2));
    int a,b;
    for(int i=0;i<N;i++){
        cin>>a>>b;
        edges.push_back({a-1,b-1});
    }
    Graph<int,int> g(edges,N);
    vector<int> isC(N);
    for(int i=0;i<N;i++){
        isC[i]=(S[i]=='c');
    }
    vector<int> ord=g.orderFromChildren();
    vector<long long> c(N),w(N);
    for(int i:ord){
        c[i]+=isC[i];
        w[i]+=(1-isC[i]);
        if(g.parent[i]!=-1){
            c[g.parent[i]]+=c[i];
            w[g.parent[i]]+=w[i];
        }
    }
    vector<long long> cw(N),ww(N),pcw(N),pww(N);
    for(int i:ord){
        if(!isC[i]){
            cw[i]+=c[i];
            ww[i]+=w[i]-1;
            pcw[i]=c[i];
            pww[i]=w[i]-1;
        }
        if(g.parent[i]!=-1){
            cw[g.parent[i]]+=cw[i];
            ww[g.parent[i]]+=ww[i];
        }
    }
    vector<long long> cww(N);
    for(int i:ord){
        if(isC[i]){
            cww[i]+=ww[i];
            cww[i]+=w[i]*cw[i];
            for(int j:g.children[i]){
                cww[i]-=w[j]*cw[j];
            }
            cww[i]+=(c[i]-1)*ww[i];
            for(int j:g.children[i]){
                cww[i]-=c[j]*ww[j];
            }
        }else{
            cww[i]+=cw[i]-pcw[i];
            cww[i]+=c[i]*(w[i]-1);
            for(int j:g.children[i]){
                cww[i]-=c[j]*w[j];
            }
            cww[i]+=(w[i]-1)*(cw[i]-pcw[i]);
            for(int j:g.children[i]){
                cww[i]-=w[j]*cw[j];
            }
            cww[i]+=c[i]*(ww[i]-pww[i]);
            for(int j:g.children[i]){
                cww[i]-=c[j]*ww[j];
            }
        }
        if(g.parent[i]!=-1){
            cww[g.parent[i]]+=cww[i];
        }
    }
    cout<<cww[0]<<endl;
}
0