fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ePdlwd
language:
C++ (gcc 8.3)
created:
11 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!