fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long int
  3. #define pll pair<ll,ll>
  4. #define vpll vector< pll >
  5. #define mpll map<ll,ll>
  6. #define MOD 1000000007
  7. #define MOD2 998244353
  8. #define all(v) v.begin(),v.end()
  9. #define s(v) v.size()
  10. #define test ll t;cin>>t;while(t--)
  11. #define vec vector<ll>
  12. #define read0(v,n) for(int i=0;i<n;i++)cin>>v[i];
  13. #define read1(v,n) for(int i=1;i<=n;i++)cin>>v[i];
  14. #define trav(a,x) for (auto& a: x)
  15. #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
  16. #define cut(x) {cout<<x;return 0;}
  17. #define print(x) {cout<<x<<nl;continue;}
  18. #define FOR(i,a,b) for(int i=a;i<=b;i++)
  19. #define FORB(i,a,b) for(int i=a;i>=b;i--)
  20. #define err1(a) {cout<<#a<<' '<<a<<nl;}
  21. #define err2(a,b) {cout<<#a<<' '<<a<<' '<<#b<<' '<<b<<nl;}
  22. #define mem(a,b) memset(a,b,sizeof(a))
  23.  
  24. #define mp make_pair
  25. #define pb push_back
  26. #define eb emplace_back
  27. #define f first
  28. #define sc second
  29. #define lb lower_bound
  30. #define ub upper_bound
  31. #define nl '\n'
  32. #include <ext/pb_ds/assoc_container.hpp>
  33. #include <ext/pb_ds/tree_policy.hpp>
  34.  
  35. using namespace __gnu_pbds;
  36. using namespace std;
  37. #define oset tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
  38. ll gcd(ll a, ll b){
  39. 	if (b==0)return a;
  40. 	return gcd(b, a % b);
  41. }
  42. ll lcm(ll a,ll b){
  43.  
  44.     return (a*b)/gcd(a,b);
  45. }
  46. ll bpow(ll a, ll b){
  47. 	ll ans=1;
  48. 	a%=MOD;
  49. 	while(b){
  50. 		if(b&1)
  51. 			ans=(ans*a)%MOD;
  52. 		b/=2;
  53. 		a=(a*a)%MOD;
  54. 	}
  55. 	return ans;
  56. }
  57. void online_judge(){
  58. 	#ifndef ONLINE_JUDGE
  59.     	freopen("input.txt", "r", stdin);
  60.     	freopen("output.txt", "w", stdout);
  61.     	#endif
  62. }
  63.  
  64.  
  65. int main(){
  66.  
  67. 	//online_judge();
  68.    	fast
  69.    	test{
  70.    		ll n,m,k;
  71.    		cin>>n>>m>>k;
  72.    		vec v(n+1,INT_MAX);
  73.    		FOR(i,1,m){
  74.    			ll u,x;cin>>u>>x;
  75.    			v[u]=x;
  76.    		}
  77.    		bool ok=1;
  78.    		map<ll,pll> ms;
  79.    		map<pll,ll> s;
  80.    		FOR(i,1,k){
  81.    			ll x,y,d;
  82.    			cin>>x>>y>>d;
  83.    			if(v[x]==INT_MAX || v[y]==INT_MAX){
  84.    				if(v[x]==INT_MAX and v[y]==INT_MAX){
  85.    					if(s.find({min(x,y),max(x,y)})==s.end()){
  86.    						s[{min(x,y),max(x,y)}]=d;
  87.    					}
  88.    					else{
  89.    						s[{min(x,y),max(x,y)}]=min(d,s[{min(x,y),max(x,y)}]);
  90.    					}
  91.    					continue;
  92.    				}
  93.    				if(v[x]==INT_MAX){
  94.    					ll a=v[y]-d;
  95.    					ll b=v[y]+d;
  96.    					if(a>b)swap(a,b);
  97.    					if(ms.find(x)==ms.end()){
  98.    						ms[x]={a,b};
  99.    					}
  100.    					else{
  101.    						ms[x]={max(a,ms[x].f),min(b,ms[x].sc)};
  102.    					}
  103.    				}
  104.    				else{
  105.    					ll a=v[x]-d;
  106.    					ll b=v[x]+d;
  107.    					if(a>b)swap(a,b);
  108.    					if(ms.find(y)==ms.end()){
  109.    						ms[y]={a,b};
  110.    					}
  111.    					else{
  112.    						ms[y]={max(a,ms[y].f),min(b,ms[y].sc)};
  113.    					}
  114.    				}
  115.    			}
  116.    			else{
  117.    				if(abs(v[x]-v[y])>d){
  118.    					ok=0;
  119.    				}
  120.    			}
  121.    		}
  122.    		trav(it,ms){
  123.    			if(it.sc.f>it.sc.sc)ok=0;
  124.    		}
  125.    		if(!ok)print("NO")
  126.    		trav(it,s){
  127.    			ll x=it.f.f,y=it.f.sc,p=it.sc;
  128.    			if(ms.find(x)==ms.end()||ms.find(y)==ms.end())continue;
  129.    			ll a=ms[x].f,b=ms[x].sc,c=ms[y].f,d=ms[y].sc;
  130.    			// if(a==INT_MAX||b==INT_MAX||c==INT_MAX||d==INT_MAX)continue;
  131.    			ll mn=c-p,mx=d+p;
  132.    			if(b<mn || a>mx)ok=0;
  133.  
  134.    		}
  135.    		if(ok)print("YES")
  136.    		print("NO")
  137.  
  138.    	}
  139.  
  140. }
Success #stdin #stdout 0.01s 5384KB
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/hRUGtH
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!