相关链接
题目传送门: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 ——————————
这题还可以用线性基搞一搞
另外,并查集撤销那里没问题,不需要可持久化
I really like your blog.. very nice colors & theme.
Did you design this website yourself or did you hire someone to do it for you?
Plz answer back as I’m looking to design my own blog
and would like to know where u got this from. appreciate it
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.
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.
Pretty! This has been a really wonderful article.
Thank you for supplying this info.
Hi there, I enjoy reading through your article post.
I like to write a little comment to support you.
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!
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!!
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.
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!
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
Good day! Do you use Twitter? I’d like to follow you if that would be okay.
I’m definitely enjoying your blog and look forward to new posts.
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.
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.
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!
It’s impressive that you are getting ideas from this article as well
as from our dialogue made at this time.
If you wish for to get a great deal from this paragraph then you have to apply such methods
to your won weblog.
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
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.
Hello, just wanted to mention, I enjoyed this blog post. It was funny.
Keep on posting!
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.
Hello friends, how is all, and what you would like to say about this post, in my
view its in fact remarkable designed for me.
Post writing is also a fun, if you be acquainted
with after that you can write otherwise it is complicated
to write.
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
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?
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.
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.
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?
Awesome post.
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!
There is certainly a lot to learn about this subject.
I love all the points you have made.
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.
I got good info from your blog