fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fo(i,a,b) for(int i=(a);i<(b);i++)
  4. #define MOD 1000000007
  5. #define MP make_pair
  6. #define PB push_back
  7. typedef long long ll;
  8.  
  9. int N, M, D, ans;
  10.  
  11. struct thing {
  12. 	ll a; int b;
  13. 	inline void OR (thing& o) { a |= o.a, b |= o.b; }
  14. 	inline bool get (int x) {
  15. 		if (x<60) return a&(1ll<<x);
  16. 		else return b&(1<<(x-60));
  17. 	}
  18. 	inline void set (int x) {
  19. 		if (x<60) a |= (1ll<<x);
  20. 		else b |= (1<<(x-60));
  21. 	}
  22. 	inline bool any () { return a||b; }
  23. } edge[90][2], can[2][1<<21];
  24.  
  25. int main () {
  26. 	scanf("%d %d %d", &N, &M, &D);
  27. 	fo(i, 0, M) {
  28. 		int a, b, c; scanf("%d %d %d", &a, &b, &c), a--, b--;
  29. 		edge[a][c].set(b);
  30. 		edge[b][c].set(a);
  31. 	}
  32.  
  33. 	can[0][0].set(0);
  34.  
  35. 	fo(d, 0, D) {
  36. 		fo(i, 0, 1<<d) {
  37. 			can[(d+1)%2][i] = can[(d+1)%2][i+(1<<d)] = {0ll, 0};
  38. 			fo(x, 0, N) if (can[d%2][i].get(x)) {
  39. 				can[(d+1)%2][i].OR(edge[x][0]);
  40. 				can[(d+1)%2][i+(1<<d)].OR(edge[x][1]);
  41. 			}
  42. 		}
  43. 	}
  44.  
  45. 	fo(i, 0, 1<<D) ans += can[D%2][i].any();
  46. 	printf("%d\n", ans);
  47. 	return 0;
  48. }
  49.  
Success #stdin #stdout 0s 52624KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/bTTrha
language:
C++14 (gcc 8.3)
created:
8 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!