Submission #4143421

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> edge[100005];
int num[100005] = {0};
int dp[100005] = {0};

int solve();

int main() {
  cin >> n >> m;
  for(int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    edge[x - 1].push_back(y - 1);
    ++num[y - 1];
  }
  cout << solve() << endl;
  return 0;
}

int solve() {
  int ans = 0;
  queue<int> qu;
  for(int i = 0; i < n; ++i)
    if(num[i] == 0) qu.push(i);
  while(qu.size() > 0) {
    int now = qu.front();
    qu.pop();
    for(int i = 0; i < edge[now].size(); ++i) {
      int to = edge[now][i];
      if(--num[to] == 0) {
        dp[to] = dp[now] + 1;
        ans = max(ans, dp[to]);
        qu.push(to);
      }
    }
  }
  return ans;
}

Submission Info

Submission Time
Task G - Longest Path
User m_tsubasa
Language C++14 (GCC 5.4.1)
Score 100
Code Size 767 Byte
Status AC
Exec Time 73 ms
Memory 6528 KiB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 22
Set Name Test Cases
All 0_00, 0_01, 0_02, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17, 1_18
Case Name Status Exec Time Memory
0_00 AC 3 ms 2560 KiB
0_01 AC 3 ms 2560 KiB
0_02 AC 3 ms 2560 KiB
1_00 AC 3 ms 2560 KiB
1_01 AC 71 ms 6528 KiB
1_02 AC 44 ms 3200 KiB
1_03 AC 73 ms 5376 KiB
1_04 AC 67 ms 4352 KiB
1_05 AC 67 ms 3840 KiB
1_06 AC 58 ms 3584 KiB
1_07 AC 54 ms 3456 KiB
1_08 AC 52 ms 3328 KiB
1_09 AC 49 ms 3200 KiB
1_10 AC 45 ms 3200 KiB
1_11 AC 60 ms 3712 KiB
1_12 AC 71 ms 5120 KiB
1_13 AC 69 ms 4992 KiB
1_14 AC 62 ms 3712 KiB
1_15 AC 60 ms 3584 KiB
1_16 AC 68 ms 4608 KiB
1_17 AC 72 ms 5632 KiB
1_18 AC 66 ms 4096 KiB