fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. typedef long long ll;
  7. typedef long double ld;
  8. typedef pair<int, int> pii;
  9. typedef pair<ll, ll> pll;
  10. typedef vector<int> vi;
  11. typedef vector<ll> vl;
  12. typedef vector<pii> vii;
  13. typedef vector<pll> vll;
  14. typedef vector<vl> matrix;
  15. #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
  16. #define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
  17. #define all(x) (x).begin(),(x).end()
  18. #define pb push_back
  19. #define ff first
  20. #define ss second
  21. #define mp make_pair
  22.  
  23. const ll inf = 2e18;
  24. const ll logi = 63;
  25.  
  26. static inline ll mul(ll a, ll b){
  27.     if(!a || !b) return 0;
  28.     __int128 x = __int128(a) * b;
  29.     return x >= inf ? inf : ll(x);
  30. }
  31.  
  32. static inline ll add(ll a, ll b){
  33.     return min(a + b, inf);
  34. }
  35.  
  36. matrix mnozenie(matrix& a, matrix& b){
  37.     int n = a.size();
  38.     matrix c(n, vl(n, 0));
  39.  
  40.     for(int i = 0; i < n; i++){
  41.         for(int k = 0; k < n; k++){
  42.             if(!a[i][k]) continue;
  43.             for(int j = 0; j < n; j++){
  44.                 if(!b[k][j]) continue;
  45.                 c[i][j] = add(c[i][j], mul(a[i][k], b[k][j]));
  46.             }
  47.         }
  48.     }
  49.  
  50.     return c;
  51. }
  52.  
  53.  
  54. int main(){
  55.     ios_base::sync_with_stdio(0);
  56.     cin.tie(0);
  57.  
  58.     ll n, m, k; cin >> n >> m >> k; k += n;
  59.  
  60.     vector<matrix> dp(logi);
  61.     dp[0].assign(3 * n + 1, vl(3 * n + 1, 0));
  62.  
  63.     for(int i = 0; i < n; i++){
  64.         dp[0][i + n][i] = 1;
  65.         dp[0][i + 2 * n][i + n] = 1;
  66.         dp[0][i][3 * n] = 1;
  67.     }
  68.     dp[0][3 * n][3 * n] = 1;
  69.  
  70.     for(int i = 0; i < m; i++){
  71.         int a, b, c; cin >> a >> b >> c; a--; b--;
  72.         int przes = n * (c - 1);
  73.         dp[0][a][b + przes]++;
  74.     }
  75.  
  76.     for(int i = 1; i < logi; i++){
  77.         dp[i] = mnozenie(dp[i - 1], dp[i - 1]);
  78.     }
  79.  
  80.     ll czy = 0;
  81.     for(int i = 0; i < n; i++) czy = add(czy, dp[logi - 1][i][3 * n]);
  82.     if(czy < k){
  83.         cout << "-1\n"; return 0;
  84.     }
  85.  
  86.     vl akt(3 * n + 1, 0); akt[3 * n] = 1;
  87.     ll wyn = 0;
  88.     for(int t = logi - 1; t >= 0; t--){
  89.         vl kand(3 * n + 1, 0);
  90.         for(int i = 0; i <= 3 * n; i++){
  91.             if(!akt[i]) continue;
  92.             for(int j = 0; j <= 3 * n; j++){
  93.                 kand[j] = add(kand[j], mul(akt[i], dp[t][j][i]));
  94.             }
  95.         }
  96.         ll spr = 0;
  97.         for(int i = 0; i < n; i++) spr = add(spr, kand[i]);
  98.         if(spr < k){
  99.             akt = kand;
  100.             wyn += (1ll << t);
  101.         }
  102.     }
  103.  
  104.  
  105.     cout << wyn << "\n";
  106.  
  107.     return 0;
  108. }
  109.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
6 6 11
1 2 1
2 3 2
3 4 2
4 5 1
5 3 1
4 6 3
stdout
copy 
4
https://ideone.com/eK3sCP
language:
C++ (gcc 8.3)
created:
9 hours 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!