Submission #10405735
Source Code Expand
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back const int MAXN = 1e5+5; vector<int>G[MAXN]; ll dp[MAXN]; int in[MAXN], n, m; queue<int> que; void read() { cin >> n >> m; for(int i=0; i<m; i++) { int a, b; cin >> a >> b; G[a].pb(b); ++in[b]; } } void prepare() { fill(dp, dp+MAXN, LLONG_MAX); for(int i=1; i<=n; i++) { if(in[i]==0) { que.push(i); dp[i]=0; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(NULL); read(); prepare(); while(!que.empty()) { int front = que.front(); que.pop(); for(int i : G[front]) { if(dp[i] == LLONG_MAX) dp[i] = dp[front]+1LL; dp[i] = max(dp[i], dp[front]+1LL); in[i]--; if(in[i] == 0) que.push(i); } } ll res = 0; for(int i=1; i<=n; i++) res = max(res, dp[i]); cout << res; }
Submission Info
Submission Time | |
---|---|
Task | G - Longest Path |
User | maximus123 |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 898 Byte |
Status | AC |
Exec Time | 32 ms |
Memory | 6912 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
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 | 3456 KB |
0_01 | AC | 3 ms | 3456 KB |
0_02 | AC | 3 ms | 3456 KB |
1_00 | AC | 3 ms | 3456 KB |
1_01 | AC | 32 ms | 6912 KB |
1_02 | AC | 17 ms | 3968 KB |
1_03 | AC | 31 ms | 5760 KB |
1_04 | AC | 28 ms | 4864 KB |
1_05 | AC | 26 ms | 4480 KB |
1_06 | AC | 28 ms | 4352 KB |
1_07 | AC | 21 ms | 4224 KB |
1_08 | AC | 20 ms | 4096 KB |
1_09 | AC | 19 ms | 3968 KB |
1_10 | AC | 17 ms | 3968 KB |
1_11 | AC | 25 ms | 4352 KB |
1_12 | AC | 31 ms | 5632 KB |
1_13 | AC | 30 ms | 5632 KB |
1_14 | AC | 26 ms | 4480 KB |
1_15 | AC | 24 ms | 4352 KB |
1_16 | AC | 29 ms | 5120 KB |
1_17 | AC | 32 ms | 6016 KB |
1_18 | AC | 28 ms | 4736 KB |