fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define ull unsigned long long 
  5. #define pb(e) push_back(e)
  6. #define sv(a) sort(a.begin(),a.end())
  7. #define sa(a,n) sort(a,a+n)
  8. #define mp(a,b) make_pair(a,b)
  9. #define vf first
  10. #define vs second
  11. #define ar array
  12. #define all(x) x.begin(),x.end()
  13. const int inf = 0x3f3f3f3f;
  14. const int mod = 1000000007; 
  15. const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
  16.  
  17. mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
  18.  
  19. bool remender(ll a , ll b){return a%b;}
  20.  
  21. //freopen("problemname.in", "r", stdin);
  22. //freopen("problemname.out", "w", stdout);
  23.  
  24. void merge(pair<ll,ll>& a, pair<ll,ll>& b , ll& d){
  25. 	if(!((a.vf <= b.vf  && a.vs >= b.vs) || (b.vf <= a.vf && b.vs >= a.vs))){
  26. 		if(min(a.vs , b.vs) + d < max(a.vf,b.vf)){
  27. 			d = -1e18;
  28. 			return;
  29. 		}
  30. 	}
  31. 	pair<ll,ll> u,v;
  32. 	u.vf = max(a.vf , b.vf - d);
  33. 	v.vf = max(b.vf , a.vf - d);
  34. 	u.vs = min(a.vs , b.vs + d);
  35. 	v.vs = min(b.vs , a.vs + d);
  36. 	a = u;
  37. 	b = v;
  38. }
  39.  
  40. void solve(){
  41. 	int n;
  42. 	cin >> n;
  43. 	ll arr[n];
  44. 	for(int i = 0; i < n; i++)arr[i] = 1e18;
  45. 	int m,k;
  46. 	cin >> m >> k;
  47. 	for(int i = 0; i < m; i++){
  48. 		ll pos , val;
  49. 		cin >> pos >> val;
  50. 		pos--;
  51. 		arr[pos] = val;
  52. 	}
  53. 	vector<pair<ll,ll>> range;
  54. 	for(int i = 0; i < n; i++){
  55. 		range.pb(mp(-1e17,1e17));
  56. 		if(arr[i] != 1e18)range[i] = mp(arr[i],arr[i]);
  57. 	}
  58. 	vector<pair<int,int>> adj[n + 1];
  59. 	string ans = "YES";
  60. 	for(int i = 0; i < k; i++){
  61. 		ll u , v , d;
  62. 		cin >> u >> v >> d;
  63. 		u--;
  64. 		v--;
  65. 		merge(range[u] , range[v],d);
  66. 		//cout << range[v].vf << ' ' << range[v].vs << ' ';
  67. 		if(d == -1e18){
  68. 			//cout << i << ' ';
  69. 			ans = "NO";
  70. 		}
  71. 	} 
  72. 	cout << ans << '\n';
  73. }
  74.  
  75. int main(){
  76. ios_base::sync_with_stdio(false);
  77. cin.tie(NULL);
  78. 	int t;cin >> t;while(t--)
  79. 	solve();
  80. 	return 0;
  81. }
Success #stdin #stdout 0.01s 5460KB
comments (?)
stdin
copy 
1
6 2 7
1 3
2 8
1 3 2
2 4 1
3 5 1
4 5 1
1 5 3
3 6 0
1 6 1
stdout
copy 
YES
https://ideone.com/jiujyz
language:
C++ (gcc 8.3)
created:
315 days ago
visibility:
secret

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!