Advertisement
Ginger_samurai

Untitled

Oct 2nd, 2020
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.17 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include<vector>
  3. #include <string>
  4. #include<algorithm>
  5. #include <iostream>
  6. #include <queue>
  7. #include<set>
  8. #include<unordered_set>
  9. #include<stack>
  10. #include<cmath>
  11. #include<math.h>
  12. #include<map>
  13. #include<unordered_map>
  14. #include<random>
  15. #include<chrono>
  16. #include <ctime>
  17. using namespace std;
  18. typedef long long ll;
  19. typedef pair<long long, long long> pll;
  20. #define mp make_pair
  21. #define fi(b, c) for(ll i = b; i <= c; i++)
  22. #define fj(b, c) for(ll j = b; j <= c; j++)
  23. #define fk(b, c) for(ll k = b; k <= c; k++)
  24. #define fq(b, c) for(ll q = b; q <= c; q++)
  25. #define fw(b, c) for(ll w = b; w <= c; w++)
  26. #define fim(b, c) for(ll i = b; i >= c; i--)
  27. #define fjm(b, c) for(ll j = b; j >= c; j--)
  28. #define fkm(b, c) for(l k = b; k >= c; k--)
  29. #define all(a) a.begin(), a.end()
  30. #define rall(a) a.rbegin(), a.rend()
  31. #define uniq(a) sort(all(a)); a.erase( unique( a.begin(), a.end() ), a.end() );
  32. // #define sz(a) (ll)(a.size())
  33. #define fs first
  34. #define sd second
  35. #define endl "\n"
  36. #define sz(x) (ll)(x.size())
  37.  
  38. const ll inf = 1e9 + 123, llinf = 1e18 + 829, ura = 684395049517, mod = 998244353;
  39. void xru() {
  40.     // 9 BOG 4EL
  41.     //  setlocale(LC_ALL, "rus");
  42.     //  freopen(".in", "r", stdin);
  43.     //  freopen(".out", "w", stdout);
  44.     ios_base::sync_with_stdio(false);
  45.     cin.tie(NULL);
  46.     cout.tie(NULL);
  47. }
  48. void run() {
  49.     cout << endl;
  50.     system("pause");
  51. }
  52. /////////////////////////////////
  53. ll n, m;
  54. vector<vector<ll>>g, rg;
  55. vector<bool> used;
  56. vector<ll> dp, order;
  57. map<pll, ll> len;
  58. /////////////////////////////////
  59.  
  60. void dfs(ll v){
  61.     used[v] = true;
  62.     for(ll to: g[v]){
  63.         if(!used[to]) dfs(to);
  64.     }
  65.     order.push_back(v);
  66. }
  67.  
  68. bool cond(ll v){
  69.     used[v] = true;
  70.     for(ll to: rg[v]){
  71.         if(!used[to]){
  72.             cout << "No";
  73.             return 0;
  74.         }
  75.     }
  76.     return 1;
  77. }
  78.  
  79. int main() {
  80.     cin >> n >> m;
  81.     g.resize(n);
  82.     rg.resize(n);
  83.     used.resize(n, false);
  84.     dp.resize(n, -1);
  85.     fi(0, m-1){
  86.         ll l, r, d;
  87.         cin >> l >> r >> d;
  88.         // if(l == 3 && r == 1) cout << "BLIN";
  89.         g[l-1].push_back(r-1);
  90.         rg[r-1].push_back(l-1);
  91.         len[{l-1, r-1}] = d;
  92.     }
  93.     // fi(0, n-1){
  94.     //     cout << i+1 << ": ";
  95.     //     for(ll to: g[i]) cout << to+1 << " ";
  96.     //     cout << endl;
  97.     // }
  98.     fi(0, n-1){
  99.         if(!used[i]) dfs(i);
  100.     }
  101.     reverse(all(order));
  102.     fi(0, n-1) used[i] = false;
  103.     fi(0, n-1){
  104.         if(!used[order[i]]){
  105.             if(!cond(order[i])) return 0;
  106.         }
  107.     }
  108.     bool first = true;
  109.     // cout << order.size() << endl;
  110.     for(ll now: order){
  111.         // cout << now + 1 << "-";
  112.         if(first) {
  113.             dp[now] = 0;
  114.             // cout << dp[now] << " ";
  115.             first = false;
  116.             continue;
  117.         }
  118.         for(ll from: rg[now]){
  119.             if(dp[now] == -1){
  120.                 dp[now] = dp[from] + len[{from, now}];
  121.             } else if(dp[now] != dp[from] + len[{from, now}]){
  122.                 cout << "No";
  123.                 return 0;
  124.             }
  125.         }
  126.         if(rg[now].empty()) dp[now] = 0;
  127.         // cout << dp[now] << ";  ";
  128.     }
  129.     cout << "Yes";
  130. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement