fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int lli;
  4.  
  5. int visited[500005];
  6.  
  7. bool iscyclic(vector<vector<int> > &ed,int st,int par)
  8. {
  9. 	visited[st]=1;
  10. 	for(int i=0;i<ed[st].size();i++)
  11. 	{
  12. 		if(!visited[ed[st][i]])
  13. 		{
  14. 		if(iscyclic(ed,ed[st][i],st))
  15. 		return true;
  16. 		}
  17. 		else if(ed[st][i]!=par)
  18. 		return true;
  19. 	}
  20. 	return false;
  21. }
  22.  
  23.  
  24. class pnt
  25. {
  26. 	public:
  27. 	int no,y;
  28. };
  29.  
  30.  
  31. int main() {
  32. 	int n,x,y;
  33. 	cin>>n;
  34. 	pnt pt[2*n];
  35. 	for(int i=0;i<n;i++)
  36. 	{
  37. 		cin>>x>>y;
  38. 		x--;
  39. 		y--;
  40. 		pt[x].no=pt[y].no=i;
  41. 		pt[x].y=y;
  42. 		pt[y].y=y;
  43. 	}
  44.  
  45. 	set<pair<int,int> > curr;
  46.  
  47. 	vector<vector<int> > mp(n);
  48.  
  49. 	int fl=1;
  50.  
  51. 	int ed=-1;
  52.  
  53. 	for(int i=0;i<2*n and ed<n;i++)
  54. 	{
  55. 		//ed+=n;
  56. 		if(pt[i].y!=i)
  57. 		{
  58. 		if(!curr.empty())
  59. 		{
  60.                 auto itr=curr.lower_bound({pt[i].y,-1});
  61.                 if(itr!=curr.begin())
  62. 				itr--;
  63. 				if(itr!=curr.end() and itr->first<pt[i].y)
  64. 				{
  65. 				//	cout<<i<<" "<<itr->first<<"\n";
  66. 				while(itr!=curr.begin() and ed<n)
  67. 				{
  68. 					int e=itr->second;
  69. 					mp[pt[i].no].push_back(e);
  70. 				    mp[e].push_back(pt[i].no);
  71. 				    ed++;
  72. 				    itr--;
  73. 				}
  74. 				if(itr==curr.begin())
  75. 				{
  76. 				int e=itr->second;
  77. 				mp[pt[i].no].push_back(e);
  78. 				mp[e].push_back(pt[i].no);
  79. 				ed++;
  80. 				}
  81. 				}
  82. 		}
  83. 		curr.insert({pt[i].y,pt[i].no});
  84. 		}
  85. 		else
  86. 		{
  87. 			curr.erase(curr.find({pt[i].y,pt[i].no}));
  88. 		}
  89. 	}   
  90.  
  91.  
  92.     if(iscyclic(mp,0,0))
  93.     fl=0;
  94.  
  95. 	for(int i=0;i<n;i++)
  96. 	{
  97. 		if(!visited[i])
  98. 		{
  99. 			//cout<<i<<" "<<"\n";
  100. 			fl=0;
  101. 			break;
  102. 		}
  103. 	}
  104.  
  105. 	if(fl==0)
  106. 	{
  107. 		cout<<"NO\n";
  108. 	}
  109. 	else
  110. 	cout<<"YES\n";
  111.  
  112. 	return 0;
  113.  
  114. }
Success #stdin #stdout 0s 4544KB
comments (?)
stdin
copy 
6
9 12
2 11
1 3
6 10
5 7
4 8
stdout
copy 
YES
https://ideone.com/5F6MKs
language:
C++14 (gcc 8.3)
created:
4 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!