結果

問題 No.1660 Matrix Exponentiation
コンテスト
ユーザー vjudge1
提出日時 2026-08-14 05:44:19
言語 C++17(gcc12)
(gcc 12.4.0 + boost 1.90.0)
コンパイル:
g++-12 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 27 ms / 2,000 ms
+ 135µs
コード長 2,156 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,782 ms
コンパイル使用メモリ 209,336 KB
実行使用メモリ 10,856 KB
最終ジャッジ日時 2026-08-14 05:44:25
合計ジャッジ時間 5,846 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void setIO(std::string)’:
main.cpp:33:16: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   33 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:34:16: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   34 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using ld = long double;
using vld = vector<ld>;
using vvld = vector<vld>;
using vs = vector<string>;
using vvs = vector<vs>;
using vb = vector<bool>;
using vvb = vector<vb>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;

#define norm_mod(x, m) (((x % m) + m) % m)
#define add_mod(a, b, m) norm_mod((a % m) + (b % m), m)
#define sub_mod(a, b, m) norm_mod((a % m) - (b % m), m)
#define mult_mod(a, b, m) norm_mod((a % m) * (b % m), m)
#define fixed(n) fixed << setprecision(n)
#define rall(x) (x).rbegin(), (x).rend()
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second

void setIO(string name = "") {
    cin.tie(0)->sync_with_stdio(0);
    if (name.size() && ifstream(name + ".in").good()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}

bool kahn(const vvll &g, vll &order) {
    order = vll();
    ll n = g.size();
    vll indegree(n, 0);
    for (ll v = 0; v < n; v++)
        for (ll u : g[v])
            indegree[u]++;
    for (ll v = 0; v < n; v++)
        if (indegree[v] == 0)
            order.push_back(v);
    for (ll i = 0; i < order.size(); i++)
        for (ll u : g[order[i]])
            if (--indegree[u] == 0)
                order.push_back(u);
    return order.size() == n;
}

void solve() {
    ll n, k;
    cin >> n >> k;
    vvll g(n);
    for (ll i = 0; i < k; i++) {
        ll r, c;
        cin >> r >> c;
        g[--r].push_back(--c);
    }
    vll order;
    bool dag = kahn(g, order);
    if (!dag) {
        cout << "-1\n";
        return;
    }
    vll dp(n, 0);
    ll max_path = 0;
    for (ll u : order) {
        for (ll v : g[u])
            dp[v] = max(dp[v], dp[u] + 1);
        max_path = max(max_path, dp[u]);
    }
    cout << max_path + 1 << '\n';
}

int main() {
    setIO();
    ll cases = 1;
    // cin >> cases;
    for (ll tc = 1; tc <= cases; tc++) {
        // cout << "Case #" << tc << ": ";
        solve();
    }
}
0