【日常小测】再次挑战NPC

题目传送门:https://oi.qizy.tech/wp-content/uploads/2016/06/water_meeting.pdf

一看这题,TM这不今年wc的T1吗?哎呀,还是不会带花树QAQ,哎呀冬令营的时候网络流搞了40分,那就来写网络流吧!
于是开始骚写网络流。 然后写完了发现过不了样例QAQ 然后想了几分钟突然发现:
如果只考虑奇偶的话,这个一个联通块里不最多只有一个半空的筐QAQ
于是最后写了一个并查集。 后来问一问,发现带花树也是可以的,但是只有80分(╯-_-)╯╧╧

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
using namespace std;

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

const int MAXN = 400000;
const int INF = 100000000;

int n,m,A[MAXN],B[MAXN],bot[MAXN];
int vout,fa[MAXN],sum[MAXN],str[MAXN];
int Q[MAXN],cnt;

inline int find(int w){
	int f=fa[w],tmp;
	while (f != fa[f]) f=fa[f];
	while (w != f) tmp=fa[w],fa[w]=f,w=tmp;
	return f;
}

inline void connect(int b, int a){
	int f1=find(a),f2=find(b);
	if (f1 != f2) fa[f1] = f2;
}

int main(){
	freopen("cpn.in","r",stdin);
	freopen("cpn.out","w",stdout);
	n = read(); m = read();
	for (int i=1;i<=m;i++) fa[i] = i;
	for (int i=1;i<=n;i++){ 
		A[i] = read(); B[i] = read();
		bot[A[i]]++; connect(A[i],B[i]);
	}	
	for (int i=1;i<=m;i++) find(i);
	for (int i=1;i<=m;i++) if (bot[i]%2)
		{sum[fa[i]]++; str[fa[i]] = i;}
	for (int i=1;i<=m;i++) if (sum[i]%2)
		{vout++; Q[++cnt]=str[i];}
	 
	printf("%d\n",vout);
	for (int i=1;i<=cnt;i++)
		printf("%d\n",Q[i]);
	
	return 0;
} 

295 thoughts to “【日常小测】再次挑战NPC”

  1. What i don’t realize is in reality how you are now not actually
    a lot more well-appreciated than you might be right now.

    You are so intelligent. You understand therefore significantly when it
    comes to this topic, produced me in my view believe it from
    a lot of numerous angles. Its like men and women are not
    interested except it’s one thing to do with Girl
    gaga! Your personal stuffs outstanding. Always deal with it up!

  2. Greate pieces. Keep posting such kind of info on your site.
    Im really impressed by it.
    Hi there, You’ve done an excellent job. I’ll certainly digg it and in my opinion recommend
    to my friends. I am sure they will be benefited from this site.

  3. Hello! I’m at work surfing around your blog from my new iphone
    3gs! Just wanted to say I love reading your blog and look forward to all your posts!
    Keep up the great work!

  4. Hey There. I found your blog using msn. This is an extremely
    well written article. I’ll be sure to bookmark it and return to
    read more of your useful information. Thanks for the post.

    I will certainly comeback.

  5. I feel this is one of the so much significant info for me.
    And i am glad reading your article. But want to
    statement on few common issues, The web site taste is wonderful, the articles is really excellent
    : D. Just right job, cheers

  6. This is very interesting, You are a very skilled blogger. I’ve joined your feed and
    look forward to seeking more of your magnificent
    post. Also, I have shared your web site in my social networks!

  7. After checking out a number of the blog articles on your site, I truly appreciate your
    technique of blogging. I bookmarked it to my bookmark site list and will be checking back soon. Take a
    look at my web site as well and tell me what you think.

  8. Howdy! This is kind of off topic but I need some help from an established blog.

    Is it very difficult to set up your own blog? I’m not very
    techincal but I can figure things out pretty fast.
    I’m thinking about creating my own but I’m not sure where to
    start. Do you have any points or suggestions?
    With thanks

  9. Greetings from California! I’m bored to tears at work so
    I decided to check out your site on my iphone during lunch break.
    I really like the information you provide here and can’t wait to take a look when I get
    home. I’m amazed at how quick your blog loaded on my cell phone ..
    I’m not even using WIFI, just 3G .. Anyways, good blog!

  10. Heya i am for the first time here. I found this board and I find It truly useful & it helped
    me out a lot. I hope to give something back and help others like you helped
    me. plenty of fish natalielise

  11. May I just say what a comfort to uncover somebody who actually knows what they’re
    talking about online. You actually realize how to
    bring a problem to light and make it important.
    More people should read this and understand this side of your story.
    I was surprised you’re not more popular given that you certainly possess the gift.

  12. Your means of describing everything in this article is actually nice, every
    one can without difficulty understand it, Thanks a lot.

    natalielise plenty of fish

  13. Thanks for the marvelous posting! I really enjoyed reading it, you could be a great author.
    I will be sure to bookmark your blog and definitely will come back in the foreseeable future.
    I want to encourage that you continue your great work, have
    a nice morning!

  14. I believe everything posted was very reasonable.
    But, what about this? suppose you typed a catchier title?
    I am not saying your content isn’t solid., but suppose you added a
    post title that makes people want more? I mean 【日常小测】再次挑战NPC – Qizy's
    Database is kinda vanilla. You ought to glance at Yahoo’s front page and watch
    how they create news titles to grab viewers
    to click. You might try adding a video or a pic or two to grab people excited about what you’ve got
    to say. Just my opinion, it could bring your website a little livelier.
    natalielise plenty of fish

  15. I think what you composed made a great deal of sense. However, think about
    this, what if you were to create a awesome headline? I mean, I don’t wish to tell you how to run your website, but suppose
    you added a title to possibly grab a person’s attention?
    I mean 【日常小测】再次挑战NPC – Qizy's Database is
    a little vanilla. You ought to peek at Yahoo’s home page and watch how they create post titles to get
    viewers to click. You might add a related video or a pic or two to grab readers interested about what you’ve written. In my
    opinion, it could bring your posts a little livelier.

  16. May I simply say what a relief to uncover someone who really
    understands what they are talking about on the internet. You actually
    understand how to bring a problem to light
    and make it important. More and more people need to read this and understand
    this side of your story. I can’t believe you’re not more popular
    given that you most certainly have the gift.

  17. Excellent post. I was checking constantly this blog and I am impressed!
    Extremely useful info specially the final section 🙂 I take care of such information a
    lot. I was looking for this certain information for a long time.
    Thank you and good luck.

  18. Hi there! I could have sworn I’ve been to this web site before but
    after looking at many of the posts I realized it’s new to me.
    Nonetheless, I’m definitely happy I stumbled
    upon it and I’ll be book-marking it and checking
    back frequently!

  19. Thanks for the marvelous posting! I seriously enjoyed reading it, you will be a great author.I will be
    sure to bookmark your blog and will come back down the road.
    I want to encourage you to definitely continue your great work,
    have a nice day!

  20. Nice post. I was checking constantly this blog
    and I am impressed! Very useful info specifically the last part
    🙂 I care for such information much. I was looking for this
    certain information for a very long time.
    Thank you and best of luck.

  21. Hmm it seems like your blog ate my first comment
    (it was super long) so I guess I’ll just sum it up what I wrote and say,
    I’m thoroughly enjoying your blog. I too am an aspiring blog writer but
    I’m still new to everything. Do you have any suggestions for rookie blog writers?
    I’d certainly appreciate it.

  22. Just wish to say your article is as astonishing. The clarity on your post is just excellent and that i
    can think you’re an expert in this subject. Well together with your permission let me to snatch your RSS feed to keep up to date with impending post.
    Thanks 1,000,000 and please keep up the enjoyable work.

  23. I was very pleased to find this great site. I need to
    to thank you for your time for this particularly wonderful read!!
    I definitely liked every part of it and i also have you book-marked to see new
    information in your website.

  24. Wow that was strange. I just wrote an extremely long comment but after I clicked submit my comment didn’t show up.
    Grrrr… well I’m not writing all that over
    again. Anyway, just wanted to say fantastic blog!

  25. Great post. I was checking constantly this blog and I am impressed!
    Extremely helpful information specially the remaining part 🙂 I
    care for such information much. I was looking for this particular information for a long time.
    Thanks and best of luck.

  26. I’m really inspired with your writing talents as well as with the
    format for your weblog. Is this a paid subject matter or did you customize it yourself?
    Either way keep up the excellent high quality writing, it’s uncommon to peer a great blog like
    this one nowadays..

  27. Please let me know if you’re looking for a author for your
    blog. You have some really good articles and I feel I would be a good asset.
    If you ever want to take some of the load off, I’d really
    like to write some articles for your blog in exchange for
    a link back to mine. Please blast me an e-mail if interested.
    Cheers!

  28. I’m not sure why but this site is loading extremely slow
    for me. Is anyone else having this issue or is it a problem
    on my end? I’ll check back later and see if the problem still exists.

  29. I’m impressed, I have to admit. Seldom do I encounter
    a blog that’s both equally educative and amusing, and let me
    tell you, you have hit the nail on the head. The issue is something that too
    few folks are speaking intelligently about. Now i’m very happy that I found this
    during my search for something relating to this.

  30. We’re a group of volunteers and starting a new
    scheme in our community. Your web site provided us with valuable info to work on. You have done
    a formidable job and our entire community will be thankful to you.

  31. Undeniably imagine that which you stated. Your favourite justification appeared
    to be at the net the simplest thing to take
    into accout of. I say to you, I certainly get irked even as other people think about concerns that they plainly don’t know about.
    You managed to hit the nail upon the highest and also
    outlined out the entire thing without having side effect , people could take
    a signal. Will probably be again to get more. Thank you

  32. Today, I went to the beach front with my children. I found a sea shell and gave it to my
    4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put the shell to her ear
    and screamed. There was a hermit crab inside and it pinched her ear.
    She never wants to go back! LoL I know this is entirely
    off topic but I had to tell someone!

  33. Hey There. I found your blog the use of msn. That is a very neatly written article.
    I will be sure to bookmark it and return to learn extra of your helpful information. Thank you
    for the post. I will definitely return.

  34. Usually I do not read post on blogs, however I wish to say that this write-up very compelled me to
    take a look at and do so! Your writing taste has been amazed me.
    Thanks, quite great post.

  35. Woah! I’m really enjoying the template/theme of
    this blog. It’s simple, yet effective. A lot of times
    it’s difficult to get that “perfect balance” between user friendliness and appearance.
    I must say you’ve done a excellent job with this.
    Additionally, the blog loads super quick for me on Chrome.

    Exceptional Blog!

  36. Excellent post. I was checking continuously this blog and I’m impressed!
    Very helpful information particularly the last part 🙂 I care for such
    info much. I was seeking this certain info for a long time.
    Thank you and best of luck.

  37. hello there and thank you for your information – I’ve certainly picked
    up something new from right here. I did however expertise
    some technical points using this site, since I experienced to reload the site lots of times previous to I could
    get it to load correctly. I had been wondering if your web hosting is OK?
    Not that I am complaining, but sluggish loading instances times will often affect your placement in google and can damage your high-quality score if ads and marketing
    with Adwords. Anyway I’m adding this RSS to my e-mail
    and can look out for much more of your respective
    intriguing content. Ensure that you update this again soon.

  38. I’ve been surfing on-line more than three hours these days, but I by no means discovered any attention-grabbing article
    like yours. It is lovely worth enough for me. In my opinion, if all web owners and
    bloggers made excellent content as you did, the web shall be much more helpful than ever before.

  39. 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 could do with some
    pics to drive the message home a little bit, but other than that, this is excellent blog.
    A fantastic read. I will certainly be back.

  40. Having read this I believed it was very enlightening.
    I appreciate you finding the time and effort to put this article together.
    I once again find myself spending a significant amount of time both reading and commenting.
    But so what, it was still worthwhile!

  41. Hey There. I found your blog using msn. This is
    a really well written article. I will be sure to bookmark it and return to read more of
    your useful info. Thanks for the post. I’ll definitely comeback.

  42. Do you mind if I quote a few of your posts
    as long as I provide credit and sources back
    to your weblog? My website is in the exact same area of interest as
    yours and my visitors would certainly benefit from a lot
    of the information you present here. Please let me know if
    this ok with you. Appreciate it!

  43. Hi, I do believe your website might be having internet
    browser compatibility issues. When I look at your blog in Safari, it
    looks fine however, if opening in I.E., it has some overlapping
    issues. I just wanted to provide you with a quick heads up!
    Other than that, excellent website!

  44. Excellent blog you have here.. It’s difficult to find quality writing like yours nowadays.
    I truly appreciate individuals like you! Take care!!

  45. Hello! This post could not be written any better! Reading through this post reminds me of my previous room mate!
    He always kept talking about this. I will forward this post
    to him. Pretty sure he will have a good read. Thanks for
    sharing!

  46. Hi there, You’ve performed a great job. I’ll certainly digg it and individually recommend to my friends. I am confident they’ll be benefited from this web site.|

  47. I’m amazed, I must say. Seldom do I come across a blog that’s both equally educative and entertaining, and let me tell you, you’ve hit the nail on the head. The issue is something which too few people are speaking intelligently about. I’m very happy that I stumbled across this in my hunt for something regarding this.|

  48. I really love your site.. Excellent colors & theme. Did you make this web site yourself? Please reply back as I’m trying to create my very own blog and want to learn where you got this from or what the theme is named. Thank you!|

  49. 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 great blog. A fantastic read. I’ll certainly be back.|

  50. You actually make it seem so easy with your presentation but I find this matter to be actually something that I think I would never understand. It seems too complicated and very broad for me. I’m looking forward for your next post, I will try to get the hang of it!|

  51. Excellent post. I was checking continuously this blog and I am impressed! Very useful information particularly the last part 🙂 I care for such information much. I was seeking this certain info for a very long time. Thank you and good luck.|

  52. Can I just say what a comfort to uncover someone who truly understands what they’re discussing over the internet. You actually understand how to bring an issue to light and make it important. More people have to check this out and understand this side of your story. I can’t believe you are not more popular because you definitely have the gift.|

  53. Greetings, I do believe your web site might be having web browser compatibility problems. Whenever I look at your blog in Safari, it looks fine however, if opening in Internet Explorer, it has some overlapping issues. I just wanted to give you a quick heads up! Apart from that, excellent website!|

  54. Great beat ! I would like to apprentice at the same time as you amend your website, how can i subscribe for a blog site? The account helped me a applicable deal. I were tiny bit familiar of this your broadcast provided shiny clear concept|

  55. Hey there! This is kind of off topic but I need some guidance from an established blog. Is it very hard to set up your own blog? I’m not very techincal but I can figure things out pretty fast. I’m thinking about making my own but I’m not sure where to begin. Do you have any points or suggestions? Thanks|

  56. I am now not certain where you are getting your info, but great topic. I needs to spend some time finding out more or figuring out more. Thank you for excellent information I used to be searching for this information for my mission.|

  57. Hi there would you mind letting me know which hosting company you’re working with? I’ve loaded your blog in 3 completely different browsers and I must say this blog loads a lot faster then most. Can you recommend a good web hosting provider at a fair price? Thanks a lot, I appreciate it!|

  58. It’s actually a great and helpful piece of information. I am glad that you shared this useful information with us. Please stay us up to date like this. Thank you for sharing.|

发表评论

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