#553405 (C++11) No.762 PDCAパス

提出ソース

結果

問題	No.762 PDCAパス
ユーザー	lunnear
提出日時	2020-09-15 20:24:21
言語	C++11 (gcc 11.4.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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 12,560 KB
testcase_01	AC	1 ms 6,944 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	1 ms 6,940 KB
testcase_04	AC	1 ms 6,940 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	1 ms 6,944 KB
testcase_07	AC	1 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	1 ms 6,940 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	WA	-
testcase_13	AC	1 ms 6,940 KB
testcase_14	AC	1 ms 6,944 KB
testcase_15	WA	-
testcase_16	WA	-
testcase_17	AC	2 ms 6,944 KB
testcase_18	WA	-
testcase_19	AC	2 ms 6,940 KB
testcase_20	WA	-
testcase_21	AC	2 ms 6,940 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	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

yukicoder

結果

テストケース

ソースコード