結果

問題 No.762 PDCAパス
ユーザー lunnearlunnear
提出日時 2020-09-15 20:24:21
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 6,261 bytes
コンパイル時間 1,768 ms
コンパイル使用メモリ 82,296 KB
実行使用メモリ 11,608 KB
最終ジャッジ日時 2023-09-04 01:55:32
合計ジャッジ時間 6,879 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 WA -
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 1 ms
4,376 KB
testcase_18 WA -
testcase_19 AC 2 ms
4,380 KB
testcase_20 WA -
testcase_21 AC 2 ms
4,376 KB
testcase_22 TLE -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0