#553405 (C++11（廃止可能性あり）) No.762 PDCAパス

• 問題: No.762 PDCAパス
• ユーザー: lunnear
• 提出日時: 2020-09-15 20:24:21
• 言語: C++11（廃止可能性あり） (gcc 13.3.0)
• 結果: WA
• 実行時間: -
• コード長: 6,261 bytes
• コンパイル時間: 1,581 ms
• コンパイル使用メモリ: 85,096 KB
• 実行使用メモリ: 13,896 KB
• 最終ジャッジ日時: 2024-06-22 01:55:28
• 合計ジャッジ時間: 5,575 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
sample	AC * 3
other	AC * 14 WA * 5 TLE * 1 -- * 18

ソースコード

#include <iostream>
#include <vector>
#include <map>

template <typename T>
class Node
{
public:
    Node(T *obj, int id, bool isDeleteAtDestractor = false)
    {
        this->obj = obj;
        this->id = id;
        this->delFlg = isDeleteAtDestractor;
    }
    ~Node()
    {
        if(this->delFlg && this->obj)
        {
            delete this->obj;
        }
    }

protected:
    T *obj;
    int id;
    bool delFlg;

public:
    T* get()
    {
        return this->obj;
    }
    int getId()
    {
        return this->id;
    }
};

template <typename T>
class Edge
{
public:
    Edge(Node<T> *a, Node<T> *b, int id)
    {
        this->a = a;
        this->b = b;
        this->id = id;
    }
    
public:
    Node<T> *a;
    Node<T> *b;
protected:
    int id;
    
public:
    int getId()
    {
        return this->id;
    }
};

template <typename T>
class Graph
{
public:
    Graph()
    {
        this->nodeId = -1;
        this->edgeId = -1;
        this->rootId = -1;
    }
    virtual ~Graph()
    {
        for(auto i = this->nodes.begin(); i != this->nodes.end(); i++)
        {
            delete (*i);
        }
        for(auto i = this->edges.begin(); i != this->edges.end(); i++)
        {
            delete (*i);
        }
    }

protected:
    std::vector<Node<T>*> nodes;
    std::vector<Edge<T>*> edges;
    int rootId;
    int nodeId;
    int edgeId;

public:
    virtual int addNode(T obj)
    {
        this->nodeId++;
        T *o = new T;
        *o = obj;
        this->nodes.push_back(new Node<T>(o, this->nodeId, true));
        
        return this->nodeId;
    }
    virtual int addEdge(int a, int b)
    {
        this->edgeId++;
        this->edges.push_back(new Edge<T>(this->nodes[a], this->nodes[b], this->edgeId));
        
        return this->edgeId;
    }
    virtual Node<T>* getNode(int id)
    {
        return this->nodes[id];
    }
    virtual Edge<T>* getEdge(int id)
    {
        return this->edges[id];
    }
    virtual std::vector<int> getNodeIds()
    {
        std::vector<int> res;
        for(auto i = this->nodes.begin(); i != this->nodes.end(); i++)
        {
            if(!(*i))
                continue;
                
            res.push_back((*i)->getId());
        }
        return res;
    }
    virtual std::vector<int> getEdgeIds()
    {
        std::vector<int> res;
        for(auto i = this->edges.begin(); i != this->edges.end(); i++)
        {
            if(!(*i))
                continue;
                
            res.push_back((*i)->getId());
        }
        return res;
    }
    virtual void removeNode(int id)
    {
        Node<T> *obj = this->nodes[id];
        delete obj;
        this->nodes[id] = nullptr;
    }
    virtual void removeEdge(int id)
    {
        Edge<T> *obj = this->edges[id];
        delete obj;
        this->edges[id] = nullptr;
    }
    virtual int countNode()
    {
        return this->getNodeIds().size();
    }
    virtual int countEdge()
    {
        return this->getEdgeIds().size();
    }
    virtual void setRoot(int root)
    {
        this->rootId = root;
    }
    virtual int getRoot()
    {
        return this->rootId;
    }
    virtual std::vector<int> getChildNode(int nodeId) = 0;
    virtual std::vector<int> getChildEdge(int nodeId) = 0;
};

template <typename T>
class DirectedGraph: public Graph<T>
{
public:
    virtual std::vector<int> getChildNode(int nodeId)
    {
        std::vector<int> res;
        std::vector<int> ids = this->getEdgeIds();
        for(auto i = ids.begin(); i != ids.end(); i++)
        {
            if(nodeId != this->getEdge(*i)->a->getId())
                continue;
            
            res.push_back(this->getEdge(*i)->b->getId());
        }
        return res;
    }
    virtual std::vector<int> getChildEdge(int nodeId)
    {
        std::vector<int> res;
        std::vector<int> ids = this->getEdgeIds();
        for(auto i = ids.begin(); i != ids.end(); i++)
        {
            int id = this->getEdge(*i)->a->getId();
            if(nodeId != id)
                continue;
            
            res.push_back(this->getEdge(*i)->getId());
        }
        return res;
    }
};

int checkAdjacent(char a, char b)
{
    static std::map<char, char> m;
    if(m.empty())
    {
        m.insert(std::make_pair('P', 'D'));
        m.insert(std::make_pair('D', 'C'));
        m.insert(std::make_pair('C', 'A'));
        m.insert(std::make_pair('A', '\0'));
    }
    
    if(m[a] == b)
        return 1;
    
    if(m[b] == a)
        return -1;
    
    return 0;
}

int main(void)
{
    DirectedGraph<char> g;
    g.setRoot(g.addNode('0'));
    
    int n, m;
    std::cin >> n >> m;
    
    char *s = new char[n + 1];
    std::cin >> s;
    s[n] = 0;
    
    for(int i = 0; s[i]; i++)
    {
        g.addNode(s[i]);
    }
    delete s;
    s = nullptr;
    
    for(int i = 0; i < m; i++)
    {
        int u, v;
        std::cin >> u >> v;
        switch(checkAdjacent(*g.getNode(u)->get(), *g.getNode(v)->get()))
        {
            case 1:
                g.addEdge(u, v);
                if(*g.getNode(u)->get() == 'P')
                    g.addEdge(g.getRoot(), u);
                break;
            
            case -1:
                g.addEdge(v, u);
                if(*g.getNode(v)->get() == 'P')
                    g.addEdge(g.getRoot(), v);
                break;
            
            default:;
        }
    }
    
    long long ans = 0;
    auto pl = g.getChildNode(g.getRoot());
    for(auto p = pl.begin(); p != pl.end(); p++)
    {
        auto dl = g.getChildNode(g.getNode(*p)->getId());
        for(auto d = dl.begin(); d != dl.end(); d++)
        {
            auto cl = g.getChildNode(g.getNode(*d)->getId());
            for(auto c = cl.begin(); c != cl.end(); c++)
            {
                ans += g.getChildNode(g.getNode(*c)->getId()).size();
                ans %= 1000000007;
            }
        }
    }

    std::cout << ans << std::endl;
}