fork download
copy 
  1. #pragma GCC optimize ("O2")
  2. #include "bits/stdc++.h"
  3. using namespace std;
  4.  
  5. ///////////// START TEMPLATE //////////////////////
  6. #if DEBUG && !ONLINE_JUDGE
  7.     #include "../debug.h"
  8. #else
  9.     #define debug(...)
  10. #endif
  11.  
  12. template<typename T>
  13. void _R(T &x){cin>>x;}
  14. template<typename T>
  15. void _R(vector<T> &x){for(auto it=x.begin();it!=x.end();it++){_R(*it);}}
  16. void R(){}
  17. template<typename T,typename... K>
  18. void R(T& head,K&... tail){_R(head);R(tail...);}
  19. template<typename T>
  20. void _W(const T &x,const char c){cout<<x;}
  21. template<typename T>
  22. void _W(const vector<T> &x,const char c){for(auto it=x.cbegin();it!=x.cend();it++){if(it!=x.cbegin())putchar(c);_W(*it,c);}}
  23. void W(){}
  24. template<typename T,typename... K>
  25. void W(const T& head,const K&... tail){_W(head,' ');cout<<(sizeof...(tail)?' ':'\n')<<flush;W(tail...);}
  26.  
  27. typedef vector<int> vi;
  28. typedef pair<int,int> ii;
  29. typedef vector<ii> vii;
  30. typedef vector<vi> vvi;
  31. typedef vector<vii> vvii;
  32. typedef map<int,int> mii;
  33. typedef map<string,int> msi;
  34. typedef long long lli;
  35.  
  36. #define pb push_back
  37. #define IT iterator
  38. #define PQ priority_queue
  39. #define GR greater
  40. #define fi first
  41. #define se second
  42. #define FOR(i,a,b) for(int i=(a);i<=(b);i++)
  43. #define REP(i,a) FOR(i,0,(int)(a)-1)
  44. #define FORd(i,a,b) for(int i=(a);i>=(b);i--)
  45. #define TR(c,it) for(auto it:(c))
  46. #define size(x) ((int)((x).size()))
  47. #define all(x) x.begin(), x.end()
  48. #define uni(x) x.erase(unique(all(x)), x.end())
  49. #define sqr(x) ((x)*(x))
  50. #define LC(x) ((x)<<1)
  51. #define RC(x) (((x)<<1)+1)
  52. #define EPS 1e-9
  53. #define EULER 2.7182818284
  54. #define MOD 1000000007
  55.  
  56. const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
  57. template<typename T> inline T gcd(T a,T b) {if(a==0)return b;return gcd(b%a,a);}
  58. template<typename T> inline void amin(T& x,T y) {if(x>y)x=y;}
  59. template<typename T> inline void amax(T& x,T y) {if(x<y)x=y;}
  60. template<typename A,typename B>
  61. class comp{public:bool operator()(const pair<A,B> &a, const pair<A,B> &b){
  62. if(a.fi!=b.fi)return a.fi<b.fi;else return a.fi>b.fi;}};
  63. lli fast_exp(lli a,lli b){lli res=1;
  64. while(b){if(b&1LL){res*=a;res%=MOD;}
  65. b>>=1LL;a*=a;a%=MOD;}
  66. return res;}
  67. //////////////// END TEMPLATE /////////////////////////
  68.  
  69. //global variables
  70. int n, m;
  71. struct edge {
  72.     int a, b;
  73.     int i;
  74.     int w;
  75. };
  76. const int N = 100000;
  77. vector<pair<int, int>> g[N];
  78. edge e[N];
  79. int a[N] = {0};
  80. int vis[N] = {0};
  81. //end global variables
  82.  
  83. void preprocess(void) {
  84.     return;
  85. }
  86.  
  87. void dfse(int x) {
  88.     vis[x] = 1;
  89.     a[x] = 1;
  90.     int v = e[x].b;
  91.     TR(g[v], u) {
  92.         if (vis[u.se] and e[u.se].i > e[x].i and e[u.se].w > e[x].w) {
  93.             a[x] = max(a[x], a[u.se] + 1);
  94.         } else if (!vis[u.se] ) {
  95.             if (e[u.se].i > e[x].i and e[u.se].w > e[x].w) {
  96.                 dfse(u.se);
  97.                 a[x] = max(a[x], a[u.se] + 1);
  98.             }
  99.         }
  100.     }
  101. }
  102.  
  103. signed main (int argc, char* argv[], char* envp[]){
  104.     //freopen("output.txt", "w", stdout);
  105.     //freopen("input.txt", "r", stdin);
  106.     ios_base::sync_with_stdio(false);
  107.     cin.tie(NULL);
  108.     cout.precision(20);
  109.     preprocess();
  110.     int teeee;
  111.     teeee = 1;
  112.     //cin >> teeee;
  113.  
  114.     FOR(zeeee, 1, teeee) {
  115.         //cout << "Case #" << zeeee << ": ";
  116.         cin >> n >> m;
  117.         REP(i, m) {
  118.             int a, b, w;
  119.             cin >> a >> b >> w;
  120.             a--, b--;
  121.             e[i] = {a, b, i, w};
  122.             g[a].pb({b, i});
  123.         }
  124.         REP(i, m) {
  125.             if (!vis[i]) {
  126.                 dfse(i);
  127.             }
  128.         }
  129.         int ans = 0;
  130.         REP(i, m) {
  131.             amax(ans, a[i]);
  132.         }
  133.         cout << ans << endl;
  134.     }
  135.  
  136.     cerr << (((double) clock()) / ((double) CLOCKS_PER_SEC)) << endl;
  137.     return 0;
  138. }
Success #stdin #stdout #stderr 0s 5644KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
stderr
copy 
0.006213
https://ideone.com/7eUS8f
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!