【BZOJ 1997】[Hnoi2010] Planar

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1997
数据生成器:http://paste.ubuntu.com/22273507/

这个题目在知道了是2-sat的情况下还是懵逼了好久QAQ
当时就想到这个图:一个正方形加上对角线.jpg(solidwork还没装,不想用word画图QAQ
发现他给的这个圆不能自交,于是每一条线就只有两种可能:
1.圆内
2.圆外
于是处理出相互干涉的线段,然后搞2-sat

最开始这么搞了,血RE
遂看题解,™有一个这个结论:
Theorem 1. If v ≥ 3 then e ≤ 3v − 6;
Theorem 2. If v ≥ 3 and there are no cycles of length 3, then e ≤ 2v − 4.
详细情况:https://en.wikipedia.org/wiki/Planar_graph
于是加特判,遂过

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<set>
#include<map>
using namespace std;

const int MAXN = 20000+9;
const int N = 200000;

int n,m,que[MAXN],L[MAXN],R[MAXN],T,nxt[N],to[N],head[MAXN],mark[MAXN],cnt;
vector<int> G[MAXN];
map<int,int> ins;

struct CMP{inline bool operator () (const int &A, const int &B) {return R[A] < R[B];}};
multiset<int,CMP>::iterator itr;
multiset<int,CMP> buf;


inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9'){c=getchar();}
	while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
	return ret;
}

inline void init(){
	n = read(); m = read(); T = 0;
	for (int i=1;i<=n;i++) G[i].clear();
	memset(head,0,sizeof(head));
	memset(mark,0,sizeof(mark));
}

#define Add_Edge(a,b) to[++T] = b,nxt[T]=head[a],head[a]=T
inline void AddEdge(int a, int b) {
	int ra=a*2+1, rb=b*2+1; a *= 2; b *= 2;
	Add_Edge(ra,b); Add_Edge(rb,a);
	Add_Edge(a,rb); Add_Edge(b,ra);
}

inline void build_map(){
	buf.clear();
	for (int i=1;i<=n;i++) {
		while (buf.size() && R[*(buf.begin())] <= i) buf.erase(buf.begin());
		for (int j=0,sz=G[i].size();j<sz;j++) 
			for (itr=buf.begin();itr!=buf.end() && R[*itr] < R[G[i][j]];itr++) 
				AddEdge(G[i][j],*itr);
		for (int j=0,sz=G[i].size();j<sz;j++) buf.insert(G[i][j]);
	}
}

bool DFS(int w) {
	if (mark[w]) return true;
	if (mark[w^1]) return false;
	mark[w] = 1; que[++cnt] = w;
	
	for (int i=head[w];i;i=nxt[i]) 
		if (!DFS(to[i])) return false;
	return true;
}

inline bool judge(){
	for (int i=2;i<=m*2+1;i+=2) if (!mark[i] && !mark[i+1]) {
		cnt = 0; if (DFS(i)) continue;
		for (int j=1;j<=cnt;j++) mark[que[j]] = 0;
		cnt = 0; if (!DFS(i+1)) return false; 
	}
	return true;
}

int main(){
	int TT = read(); while (TT--) { init();
		for (int i=1;i<=m;i++) L[i] = read(), R[i] = read();
		for (int i=1;i<=n;i++) que[i] = read(), ins[que[i]] = i;
		for (int i=1;i<=m;i++) {
			L[i] = ins[L[i]]; R[i] = ins[R[i]];
			if (L[i] > R[i]) swap(L[i], R[i]);
			G[L[i]].push_back(i);
		}
		if (m > 3*n-6) printf("NO\n");
		else {
			build_map();
			if (judge()) printf("YES\n");
			else printf("NO\n");
		}
	} 
	return 0;
}

187 thoughts to “【BZOJ 1997】[Hnoi2010] Planar”

  1. Hi there! I realize this is somewhat off-topic but I had to ask.

    Does operating a well-established website such as yours require a massive
    amount work? I’m brand new to writing a blog but I do write in my diary on a daily basis.
    I’d like to start a blog so I will be able to share my own experience and thoughts online.
    Please let me know if you have any suggestions or
    tips for brand new aspiring blog owners. Appreciate it!

  2. I’m now not certain the place you’re getting
    your info, however great topic. I must spend some time learning much more or figuring out more.
    Thank you for wonderful information I used to be looking for this information for my mission.

  3. Hello there! This is my first comment here so I just wanted to give a
    quick shout out and tell you I really enjoy reading through
    your posts. Can you recommend any other blogs/websites/forums that cover the same topics?
    Appreciate it!

  4. Hello there, I found your blog via Google whilst searching for a similar matter, your
    website got here up, it seems good. I’ve bookmarked it in my google bookmarks.

    Hi there, simply become aware of your blog via Google, and found that it’s truly informative.
    I’m going to be careful for brussels. I’ll appreciate should you
    continue this in future. Lots of other people can be
    benefited from your writing. Cheers!

  5. I’m really impressed with your writing skills and also with the
    layout on your weblog. Is this a paid theme or did you modify it
    yourself? Either way keep up the excellent quality writing, it is rare to see a great blog like this one
    today.

  6. Whoa! This blog looks exactly like my old one! It’s on a entirely
    different topic but it has pretty much the same layout and design. Superb choice of colors!

    pof natalielise

  7. I like the helpful information you provide in your articles.

    I’ll bookmark your weblog and check again here regularly. I’m quite certain I will learn plenty
    of new stuff right here! Good luck for the next!

  8. What i do not realize is actually how you are not actually much more
    neatly-preferred than you may be now. You are so intelligent.

    You understand thus significantly with regards to this matter, produced me personally consider it from numerous various
    angles. Its like men and women aren’t involved until it’s one thing to do with
    Lady gaga! Your personal stuffs excellent. At all times take care of it up!
    natalielise plenty of fish

  9. Have you ever thought about including a little bit more than just your articles?
    I mean, what you say is important and all. But imagine if
    you added some great visuals or video clips to give your posts more, “pop”!
    Your content is excellent but with images and clips,
    this site could definitely be one of the very best in its field.
    Great blog!

  10. My programmer is trying to convince me to move to .net
    from PHP. I have always disliked the idea because of the expenses.
    But he’s tryiong none the less. I’ve been using WordPress on various websites for about a year and am nervous about switching to another platform.
    I have heard great things about blogengine.net. Is there a
    way I can import all my wordpress posts into it? Any help would be greatly appreciated!

  11. My programmer is trying to persuade me to move to .net from PHP.

    I have always disliked the idea because of the expenses.
    But he’s tryiong none the less. I’ve been using Movable-type on numerous websites for about a year and am anxious about switching to another platform.
    I have heard great things about blogengine.net.

    Is there a way I can import all my wordpress content into it?
    Any kind of help would be greatly appreciated!

  12. This design is incredible! You obviously know how to keep
    a reader entertained. Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!) Great job.
    I really enjoyed what you had to say, and more than that, how you presented it.
    Too cool!

  13. always i used to read smaller articles or reviews that as well clear their motive,
    and that is also happening with this piece of writing which
    I am reading at this place.

  14. I don’t even know how I ended up here, but
    I thought this post was great. I do not know who you are but
    certainly you’re going to a famous blogger if you are not already 😉 Cheers!

  15. Hi there! Someone in my Facebook group shared this site with us so I came to take a look.

    I’m definitely loving the information. I’m bookmarking and
    will be tweeting this to my followers! Excellent blog and amazing style and design.

  16. hey there and thank you for your information – I have definitely picked up something new
    from right here. I did however expertise some technical issues using
    this site, since I experienced to reload the website lots of times previous to I could
    get it to load properly. I had been wondering if your web
    hosting is OK? Not that I’m complaining, but slow loading instances times will very frequently affect your placement in google and
    can damage your high quality score if advertising and marketing with
    Adwords. Well I’m adding this RSS to my e-mail and could look
    out for a lot more of your respective intriguing content.

    Make sure you update this again very soon.

  17. Howdy! This post couldn’t be written any better!

    Reading this post reminds me of my previous room mate!
    He always kept talking about this. I will forward this article to him.
    Pretty sure he will have a good read. Thanks for sharing!

  18. Sweet blog! I found it while surfing around on Yahoo News.
    Do you have any suggestions on how to get listed in Yahoo News?
    I’ve been trying for a while but I never seem to get there!
    Cheers

  19. Woah! I’m real caressing the template/theme of this parcel. It’s orbicular, yet powerful. A lot of present it’s assailant to get that “perfect balance” between usability and pretense. I staleness say you eff through a excellent job with this. Also, the blog loads extremely excitable for me on Cyberspace someone. Excellent Diary!

  20. After looking at a handful of the blog posts on your site, I really appreciate your technique of writing a blog.

    I book-marked it to my bookmark site list and will be checking back in the near future.
    Take a look at my web site too and tell me how you feel.

  21. Undeniably believe that that you stated. Your favourite justification seemed to be
    on the net the simplest thing to remember of. I say to you, I definitely get
    irked whilst other people think about worries that they just do
    not know about. You controlled to hit the nail upon the top as well as defined
    out the whole thing with no need side-effects , folks could take a signal.
    Will probably be again to get more. Thank you

  22. I am curious to find out what blog platform you have been using?
    I’m experiencing some minor security issues with my latest website and
    I would like to find something more safeguarded.
    Do you have any suggestions?

  23. Wow, awful journal layout! How nightlong acquire you been spouting a blog for? you tidy blogging sensing wanton. The gross glint of your website is magnificent, as smartly as the acceptance!

  24. Admiring the time and energy you put into your
    blog and in depth information you present. It’s good to come across a blog every once in a while that isn’t the same old rehashed material.
    Fantastic read! I’ve bookmarked your site and I’m including your RSS feeds to
    my Google account.

  25. It’s a shame you don’t have a donate button! I’d certainly
    donate to this brilliant blog! I guess for now i’ll settle for book-marking and adding
    your RSS feed to my Google account. I look forward to new updates and will
    talk about this site with my Facebook group. Talk soon!

  26. I’m impressed, I must say. Seldom do I come
    across a blog that’s both equally educative and amusing, and let me tell you, you’ve
    hit the nail on the head. The problem is something too few people are speaking
    intelligently about. I am very happy that I stumbled across this
    during my search for something concerning this.

  27. You prefabricated affirmative overnice points there. I did a procedure on the present and regenerate nearly all set way go along with with your leger.

  28. Hi there i am kavin, its my first occasion to commenting anywhere,
    when i read this paragraph i thought i could also
    make comment due to this sensible article.

  29. Hi, i feel that i noticed you visited my website so i came to return the choose?.I
    am attempting to find things to enhance my website!I suppose its
    adequate to make use of a few of your ideas!!

  30. I know this if off topic but I’m looking into starting my own weblog
    and was curious what all is required to get setup? I’m assuming having a blog like yours would cost a pretty penny?
    I’m not very web savvy so I’m not 100% sure. Any suggestions or advice would be greatly appreciated.

    Kudos

  31. Its such as you read my mind! You seem to understand a lot
    about this, such as you wrote the ebook in it or something.
    I believe that you could do with some % to drive the message
    house a bit, but other than that, that is wonderful blog.
    An excellent read. I’ll certainly be back.

  32. My crony recommended I power equal this web parcel. He was totally appropriate. This airman genuinely made my day. You cann’t envisage conscionable how some experience I had spent for this info! Thanks!

  33. This is rattling newsworthy, You are a really practiced blogger. I possess joined your supply and sensing forward to tag writer of your magnificent business. Also, I’ve shared your web tract in my neighbourly networks!

  34. Its like you read my mind! You appear to know a lot about this,
    like you wrote the book in it or something. I think that you could do with some pics to
    drive the message home a bit, but other than that,
    this is excellent blog. An excellent read. I’ll
    certainly be back.

  35. After exploring a handful of the blog posts on your site, I seriously like your
    way of writing a blog. I book marked it to my bookmark webpage list and will be checking back in the near future.

    Please visit my website too and tell me what you think.

  36. Hey there this is kind of of off topic but I was wanting
    to know if blogs use WYSIWYG editors or if you have to manually code with HTML.
    I’m starting a blog soon but have no coding skills so I wanted to
    get guidance from someone with experience. Any help would be enormously appreciated!

  37. Normally I do not learn post on blogs, however I would
    like to say that this write-up very forced me to take a look at and do it!

    Your writing taste has been surprised me. Thank you,
    quite great post.

  38. Wow! This can be one of the most useful blogs we have ever come across on thesubject. Basically fantastic post! I am also an expert in this topic therefore I can understand your hard work.

  39. Simply desire to say your article is as surprising.
    The clarity in your post is just cool and i can assume you are an expert on this subject.
    Fine with your permission let me to grab your RSS feed to
    keep up to date with forthcoming post. Thanks a million and
    please continue the enjoyable work.

  40. Definitely consider that which you stated.
    Your favourite reason seemed to be on the web the simplest thing to bear in mind of.
    I say to you, I definitely get irked at the same time as people think about concerns that they plainly don’t know about.
    You managed to hit the nail upon the highest and defined out the whole thing without having
    side-effects , other folks can take a signal. Will probably be again to
    get more. Thank you

  41. “4 Songs for the Club” Is a 4 song CD-EP from B-Rock, For Dj’s and Bars and Dance clubs ..”Dance”Features Rockman doing the electronic Vocals on the Chorus. A hand clapping song to get people on tha dance floor ….”Mix It With Tha Water”. Features B-Rocks Team member Pif .. Tha song is an urban street tale with a great Trap Beat….”I Like It Straight” is Bound to be a New Club/ Bar Anthem for the DJ’s to get the crowds up on their feet and to get another drink..LOL…and “Crack Them bottle (Get Fucked Up)” well that’s a story that all party goers live on the weekend! … 4 Dance Hits 4 tha Club.. a great EP for any DJ to have

  42. I love your blog.. very nice colors & theme. Did you make this website yourself or did you
    hire someone to do it for you? Plz respond as I’m looking
    to design my own blog and would like to know where u got this from.
    appreciate it

  43. Somebody necessarily lend a hand to make significantly posts I might state.
    This is the very first time I frequented your web page and up
    to now? I amazed with the research you made to create this particular put up extraordinary.
    Magnificent task!

  44. Its like you read my mind! You appear to know so much about this, like you wrote the book
    in it or something. I think that you can do with some pics to drive the message home a little
    bit, but other than that, this is great blog. An excellent
    read. I’ll definitely be back.

  45. Woah! I’m really digging the template/theme of this site.
    It’s simple, yet effective. A lot of times it’s tough to get that “perfect balance” between usability and appearance.
    I must say you’ve done a superb job with this. Additionally, the blog
    loads very quick for me on Internet explorer. Superb Blog!

  46. Great goods from you, man. I have understand your stuff previous to and you’re just extremely wonderful.

    I actually like what you have acquired here, certainly like what you’re stating and the way in which you say it.
    You make it entertaining and you still care for to keep it wise.
    I cant wait to read much more from you. This is actually a
    great web site.

  47. I do not know if it’s just me or if perhaps everyone else
    experiencing problems with your blog. It appears as though some of the text within your
    posts are running off the screen. Can someone
    else please provide feedback and let me know if this is happening to them too?
    This might be a problem with my internet browser because I’ve had this happen before.
    Many thanks

发表评论

电子邮件地址不会被公开。 必填项已用*标注