fork download
  1. #include <cstdio>
  2. #include <vector>
  3. #include <queue>
  4. #include <cstring>
  5. #include <iostream>
  6.  
  7. using namespace std;
  8.  
  9. #define MAXN 200005
  10. #define pb push_back
  11.  
  12. struct edge {
  13. int v, c, i, d;
  14. edge(int v, int c, int i, int d) : v(v), c(c), i(i), d(d) {}
  15. };
  16.  
  17. typedef vector<vector<edge> > graph;
  18.  
  19. int n, m, d[MAXN], f[MAXN];
  20. graph g;
  21.  
  22. int main() {
  23. scanf("%d %d", &n, &m);
  24. g = graph(n);
  25. for(int i = 0; i < m; i++) {
  26. int a, b, c; scanf("%d %d %d", &a, &b, &c);
  27. a--; b--;
  28. g[a].pb(edge(b,c,i,0));
  29. g[b].pb(edge(a,c,i,1));
  30. f[a] += c;
  31. f[b] += c;
  32. }
  33.  
  34. for(int i = 0; i < n; i++) {
  35. f[i] /= 2;
  36. }
  37.  
  38. memset(d, -1, sizeof(d));
  39. queue<int> Q;
  40. Q.push(0);
  41. while(!Q.empty()) {
  42. int u = Q.front(); Q.pop();
  43.  
  44. for(size_t i = 0; i < g[u].size(); i++) {
  45. int id = g[u][i].i;
  46. if(d[id] == -1) {
  47. d[id] = g[u][i].d;
  48.  
  49. int v = g[u][i].v;
  50. f[v] -= g[u][i].c;
  51. if(v != n-1 && f[v] == 0) {
  52. Q.push(v);
  53. }
  54. }
  55. }
  56. }
  57.  
  58. for(int i = 0; i < m; i++) {
  59. printf("%d\n", d[i]);
  60. }
  61. }
  62.  
Not running #stdin #stdout 0s 0KB
stdin
Standard input is empty
stdout
Standard output is empty