【BZOJ 3237】[AHOI2013] 连通图

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3237

解题报告

这个题目,真心没辙
最开始想,我们可以搞一个像Sparse_Table一样的玩意,然后用O(n)的时间单次合并并查集
然而这样的复杂度最后算下来和暴力没差多少QAQ
所以看了题解,写了网上提到的分治算法
感觉好神!
不是整体二分,也不是CDQ,就是分治,但好神!
赶紧Mark

Code

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 100000+9;
const int M = 1000000+9; 
const int SGZ = 5;

int u[M],v[M],is_del[M],vout[N],idx;
int fa[N],n,m,k,sz[N],edg[N][SGZ];

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

namespace Union_Find_Set{
	#define UFS Union_Find_Set
	int t1[M*5],t2[M*5],cnt;
	
	inline int find(int w){
		int f = fa[w], tmp;
		while (fa[f] != f) f = fa[f];
		while (w != f) t1[++cnt] = w, t2[cnt] = fa[w], fa[w] = f, w = t2[cnt];
		return f; 
	}
	
	inline void Union(int a, int b) {
		int f1 = find(a), f2 = find(b); 
		if (f1 != f2) ++cnt, fa[t1[cnt]=t2[cnt]=f1] = f2; 
	}
	
	inline void reset(int Tag) {
		for (;cnt>Tag;cnt--) 
			fa[t1[cnt]] = t2[cnt];
	}
};

void solve(int l, int r){
	int cur_time = UFS::cnt; 
	if (l == r) {
		vout[l] = 1; 
		for (int i=1,w;i<=sz[l] && vout[l];i++) { 
			w = edg[l][i];
			if (UFS::find(u[w]) != UFS::find(v[w])) vout[l] = 0;
		} 
		UFS::reset(cur_time);
	} else {
		int mid = l + r + 1 >> 1; ++idx; 
		for (int i=mid;i<=r;i++) for (int j=1;j<=sz[i];j++) is_del[edg[i][j]] = idx;
		for (int i=l;i<mid;i++) for (int j=1,w;j<=sz[i];j++) {
			w = edg[i][j];
			if (is_del[w] != idx) UFS::Union(u[w],v[w]);
		}
		solve(mid,r);
		UFS::reset(cur_time); ++idx;
		for (int i=l;i<mid;i++) for (int j=1;j<=sz[i];j++) is_del[edg[i][j]] = idx;
		for (int i=mid;i<=r;i++) for (int j=1,w;j<=sz[i];j++) {
			w = edg[i][j];
			if (is_del[w] != idx) UFS::Union(u[w],v[w]);
		}
		solve(l,mid-1);
		UFS::reset(cur_time);
	}
}

int main(){
	n = read(); m = read();
	for (int i=1;i<=n;i++) fa[i] = i;
	for (int i=1;i<=m;i++) u[i] = read(), v[i] = read();
	k = read();
	for (int i=1;i<=k;i++) {
		sz[i] = read();
		for (int j=sz[i];j;--j) 
			is_del[edg[i][j] = read()] =-1;
	} 
	for (int i=1;i<=m;i++) if (~is_del[i]) UFS::Union(u[i],v[i]);
	solve(1,k);
	for (int i=1;i<=k;i++) puts(vout[i]?"Connected":"Disconnected");
	return 0; 
}

感觉并查集撤销那里,应该用持久化并查集才对吧
感觉用栈的话,时间复杂度不对啊

另外,看看Memphis不到1s的算法,应该是有什么奇技淫巧
但找不到任何相关资料QAQ

—————————— UPD 2017.2.1 ——————————
这题还可以用线性基搞一搞
另外,并查集撤销那里没问题,不需要可持久化

32 thoughts to “【BZOJ 3237】[AHOI2013] 连通图”

  1. I am extremely impressed with your writing skills as well as
    with the layout on your blog. Is this a paid theme or did
    you customize it yourself? Anyway keep up the nice quality writing, it’s rare to see a nice blog
    like this one nowadays.

  2. Hey I know this is off topic but I was wondering if you knew of any widgets I could add to my blog that automatically tweet my newest twitter updates.
    I’ve been looking for a plug-in like this for quite some
    time and was hoping maybe you would have some experience with something
    like this. Please let me know if you run into anything.
    I truly enjoy reading your blog and I look forward to your new updates.

  3. It’s the best time to make some plans for the longer term and it’s time to be happy.
    I have read this post and if I could I want to suggest you few fascinating
    issues or tips. Maybe you could write next articles relating to this article.
    I desire to learn more issues about it!

  4. A motivating discussion is definitely worth comment.
    There’s no doubt that that you ought to write more about this subject matter, it may not be a taboo subject but usually people do not talk about these
    subjects. To the next! Many thanks!!

  5. Can I simply say what a relief to discover someone who genuinely understands
    what they are discussing on the net. You certainly understand how to bring a problem to light
    and make it important. More people have to read this and understand this side of your story.

    I can’t believe you are not more popular because you certainly possess the
    gift.

  6. First off I would like to say great blog! I had a quick question in which I’d like to ask if you
    do not mind. I was interested to find out how you center yourself and clear your
    head prior to writing. I have had a difficult time
    clearing my mind in getting my thoughts out there. I do take pleasure in writing but it just seems like the first 10 to
    15 minutes are lost simply just trying to figure out how to begin. Any suggestions or tips?

    Cheers!

  7. I believe that is among the so much significant information for me.
    And i’m happy studying your article. But wanna statement
    on few normal things, The website taste is great, the articles
    is actually great : D. Just right task, cheers

  8. Great post. I was checking constantly this blog and I am impressed!

    Very helpful info specially the last part 🙂 I care for such information much.
    I was looking for this certain information for a very long time.
    Thank you and good luck.

  9. Greate pieces. Keep writing such kind of information on your site.
    Im really impressed by it.
    Hi there, You have performed an excellent job. I’ll definitely digg it and for my part recommend to my friends.
    I am sure they’ll be benefited from this site.

  10. When I initially commented I clicked the “Notify me when new comments are added” checkbox and now each time a
    comment is added I get four e-mails with the same comment.
    Is there any way you can remove me from that service?
    Thanks a lot!

  11. I feel that is one of the most important info
    for me. And i’m glad reading your article. However want
    to statement on some normal things, The site taste is
    ideal, the articles is truly nice : D. Just right activity, cheers

  12. I’ve been surfing on-line greater than three hours nowadays, but I never discovered any fascinating article like yours. It is lovely price sufficient for me. In my opinion, if all web owners and bloggers made just right content as you did, the internet will probably be a lot more helpful than ever before.

  13. My spouse and I stumbled over here coming from a different page and thought I may as well check things out.

    I like what I see so now i am following you. Look forward to exploring your web page repeatedly.

  14. This is really interesting, You’re an overly skilled blogger.
    I’ve joined your rss feed and stay up for searching for extra of
    your wonderful post. Additionally, I have shared your site in my social networks

  15. Hi! Do you know if they make any plugins to safeguard against hackers?
    I’m kinda paranoid about losing everything I’ve worked hard on. Any suggestions?

  16. I believe what you typed was actually very reasonable.
    However, consider this, what if you were to create a awesome post title?
    I ain’t suggesting your content is not good, but
    suppose you added a post title that makes people desire more?
    I mean 【BZOJ 3237】[AHOI2013] 连通图 –
    Qizy's Database is a little vanilla. You ought to look at Yahoo’s home page and
    note how they create post titles to get people to click.
    You might try adding a video or a related pic or
    two to grab people interested about everything’ve got
    to say. In my opinion, it could make your blog a little
    bit more interesting.

  17. Just wish to say your article is as amazing.
    The clarity in your post is simply great and i can assume you’re an expert on this subject.
    Fine with your permission allow me to grab your feed
    to keep up to date with forthcoming post. Thanks a million and please continue
    the gratifying work.

  18. At this time it seems like BlogEngine is the top blogging
    platform out there right now. (from what I’ve read) Is that what you’re using
    on your blog?

  19. When someone writes an piece of writing he/she retains the idea of a user in his/her brain that
    how a user can know it. So that’s why this article is perfect.

    Thanks!

  20. We are a group of volunteers and starting a new scheme in our
    community. Your web site provided us with valuable information to work on. You have done a formidable job and our whole
    community will be grateful to you.

Leave a Reply

Your email address will not be published. Required fields are marked *