結果

問題 No.1660 Matrix Exponentiation
ユーザー yamakeyamake
提出日時 2021-08-28 12:20:55
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 141 ms / 2,000 ms
コード長 2,723 bytes
コンパイル時間 1,777 ms
コンパイル使用メモリ 186,036 KB
実行使用メモリ 31,684 KB
最終ジャッジ日時 2024-05-01 15:49:38
合計ジャッジ時間 4,418 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 22 ms
22,172 KB
testcase_10 AC 22 ms
22,052 KB
testcase_11 AC 19 ms
22,180 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 94 ms
26,812 KB
testcase_20 AC 68 ms
24,456 KB
testcase_21 AC 87 ms
15,680 KB
testcase_22 AC 15 ms
13,956 KB
testcase_23 AC 42 ms
15,560 KB
testcase_24 AC 125 ms
31,684 KB
testcase_25 AC 92 ms
30,088 KB
testcase_26 AC 141 ms
31,684 KB
testcase_27 AC 76 ms
17,300 KB
testcase_28 AC 139 ms
29,756 KB
testcase_29 AC 90 ms
17,280 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function 'void Graph::solve()':
main.cpp:88:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   88 |         for(auto& [child,len]:v.child){
      |                   ^

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define debug(output) if(debugFlag)cout<<#output<<"= "<<output<<endl
using lint = long long;
typedef pair<int,int> P;
const bool debugFlag=true;
const lint linf=1e18+7;
const lint inf=1e9+7;
const int MOD=1000000007;
struct Node{
  int no;//number of node
  int col;//color of binary_graph
  long long dist;//distance of arbitrary node
  int group;//group number of disconnected graph
  int indegree;//indegree of this node
  bool seen;
  vector<pair<Node*,long long>> child;//chidren of this node
  vector<pair<Node*,int>> par;//parretns of this node
  void build(int i){
    no=i;col=0;dist=inf;
    group=0;indegree=0;seen=false;
  }
};
bool operator >(const Node &a,const Node &r){
        return a.dist > r.dist;
    };
struct Graph{
    int n;
    bool direct;
    vector<Node> node;
    Graph(int N){
        n=N;
        node.resize(n+1);
        for(int i=1;i<=n;++i){
            node[i].build(i);
        }
    }
    void input(int m,bool flag){
        //choose direct or undirect
        direct=flag;
        for(int i=0;i<m;++i){
            int l=1;
            int a,b;cin>>a>>b;//>>l;
            node[a].child.push_back({&node[b],l});
            if(!direct){
                node[b].child.push_back({&node[a],l});
            }
            else{
                node[b].par.push_back({&node[a],l});
                node[b].indegree++;
            }
        }
    }
    vector<Node> topological_sort(){
        //return the least lexical order in the topological sorted array
        priority_queue<int,vector<int>,greater<int>> que;
        vector<Node> res;
        for(int i=1;i<=n;++i){
            if(node[i].indegree==0){
                que.push(i);
            }
        }
        while(!que.empty()){
            int buf=que.top();que.pop();
            int num=node[buf].child.size();
            res.push_back(node[buf]);
            for(int i=0;i<num;++i){
                node[buf].child[i].first->indegree--;
                if(node[buf].child[i].first->indegree==0){
                    que.push(node[buf].child[i].first->no);
                }
            }
        }
        return res;
    }
    void solve(){
      auto V=topological_sort();
      if(V.size()!=n){
        cout<<-1<<"\n";
        return;
      }
      vector<int> dp(n+5,0);
      int res=0;
      for(auto& v:V){
        for(auto& [child,len]:v.child){
          dp[child->no]=max(dp[child->no],dp[v.no]+1);
          res=max(res,dp[child->no]);
        }
      }
      cout<<res+1<<"\n";
    }
};
signed main(){
  int n,m;cin>>n>>m;
  Graph g(n);
  g.input(m,true);
  g.solve();
  return 0;
}
0