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
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 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