【CodeChef GRAPHCNT】[May Challenge 2015] Counting on a directed graph

相关链接

题目传送门:https://www.codechef.com/problems/GRAPHCNT
数据生成器:http://paste.ubuntu.com/24319212/
神犇题解Ⅰ:http://blog.csdn.net/a710128/article/details/49913553
神犇题解Ⅱ:http://www.cnblogs.com/meowww/p/6475952.html

解题报告

就是支配树的板题?

我们可以用Lengauer Tarjan算法在$O(n \alpha (n))$的时间复杂度内解决这个问题
也可以求出所有的半支配点,然后用灭绝树来搞,时间复杂度:$O(n \log n)$
另外之前我还看到一种非常鬼畜地LCT+灭绝树地做法,时间复杂度跑起来像:$O(n \log n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = 1500009;

int n,m;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	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;
}

class Dominator_Tree{
	int dom[N],pre[N],head[N],nxt[M],to[M],que[N],anc[N];
	int dfs_cnt,dfn[N],idom[N],semi[N],bst[N],ufs[N],sz[N];
	public: 
		inline void AddEdge(int u, int v) {
			AddEdge(head, u, v);
			AddEdge(pre, v, u);	
		}
		inline void build() {
			DFS(1);
			for (int i=dfs_cnt,w;w=que[i],i>1;i--) {
				for (int j=pre[w];j;j=nxt[j]) {
					if (dfn[to[j]]) {
						update(to[j]);
						if (dfn[semi[bst[to[j]]]] < dfn[semi[w]])
							semi[w] = semi[bst[to[j]]];
					}
				}
				AddEdge(dom, semi[w], w);
				ufs[w] = anc[w]; w = que[i-1];
				for (int j=dom[w];j;j=nxt[j]) {
					update(to[j]);
					if (semi[bst[to[j]]] == w) idom[to[j]] = w;
					else idom[to[j]] = bst[to[j]];
				}
			}
			for (int i=2,w;w=que[i],i<=dfs_cnt;i++)
				idom[w] = ((idom[w] == semi[w])? idom[w]: idom[idom[w]]);
		}
		inline LL solve() {
			LL ret = dfs_cnt * (dfs_cnt - 1ll) / 2ll; 
			for (int i=dfs_cnt,w;w=que[i],i>1;i--) { 
				if (++sz[w], idom[w] != 1) sz[idom[w]] += sz[w];
				else ret -= (sz[w] - 1ll) * sz[w] / 2ll;
			} return ret;
		}
	private:
		inline void AddEdge(int *arr, int u, int v) {
			static int E = 1; 
			to[++E] = v; nxt[E] = arr[u]; arr[u] = E;
		}	
		void DFS(int w) {
			dfn[w] = ++dfs_cnt; que[dfs_cnt] = w;
			bst[w] = semi[w] = ufs[w] = w;
			for (int i=head[w];i;i=nxt[i]) 
				if (!dfn[to[i]]) anc[to[i]] = w, DFS(to[i]);
		}
		int update(int w) {
			if (ufs[w] == w) return w;
			int tmp = update(ufs[w]);
			if (dfn[semi[bst[ufs[w]]]] < dfn[semi[bst[w]]])
				bst[w] = bst[ufs[w]];
			return ufs[w] = tmp;
		}
}DMT;

int main() {
	n = read(); m = read();
	for (int i=1,u,v;i<=m;i++) {
		u = read(); v = read();
		DMT.AddEdge(u, v);
	}
	DMT.build();
	cout<<DMT.solve();
	return 0;
}

37 thoughts to “【CodeChef GRAPHCNT】[May Challenge 2015] Counting on a directed graph”

  1. 865507 942853Water-resistant our wales in advance of when numerous planking. The certain wales surely are a selection of heavy duty snowboards that this height ones would be exactly the same in principle as a new shell planking having said that with significantly much more height to help you thrust outward within the evening planking. planking 143676

  2. 834195 79373This design is wicked! You certainly 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!) Excellent job. I really loved what you had to say, and more than that, how you presented it. Too cool! 151835

  3. 191392 814827 I discovered your blog internet site on google and check a couple of of your early posts. Continue to maintain up the extremely great operate. I just additional up your RSS feed to my MSN News Reader. Seeking forward to reading a lot more from you later on! 45876

  4. 458334 784176If you are still on the fence: grab your favorite earphones, head down to a Finest Buy and ask to plug them into a Zune then an iPod and see which 1 sounds better to you, and which interface makes you smile a lot more. Then you will know which is correct for you. 651350

  5. I believe this is one of the such a lot vital information for me.
    And i am glad studying your article. But should commentary on some basic things,
    The website taste is great, the articles is
    really great : D. Just right process, cheers

  6. 749903 902361Normally I do not learn post on blogs, nevertheless I would like to say that this write-up quite pressured me to look at and do so! Your writing style has been surprised me. Thank you, quite wonderful post. 765604

  7. 882168 417248Your talent is actually appreciated!! Thank you. You saved me a lot of frustration. I switched from Joomla to Drupal towards the WordPress platform and Ive fully embraced WordPress. Its so significantly easier and easier to tweak. Anyway, thanks again. Awesome domain! 290163

  8. 351698 394649I added this article to my favorites and strategy to return to digest more soon. Its straightforward to read and recognize as nicely as intelligent. I truly enjoyed my first read by means of of this article. 694432

  9. Greetings! This is my first visit to your blog! We are a
    team of volunteers and starting a new project in a community in the same niche.

    Your blog provided us useful information to work
    on. You have done a extraordinary job!

  10. I’m curious to find out what blog platform you happen to be utilizing?
    I’m experiencing some small security issues with my latest website and I’d like to
    find something more secure. Do you have any recommendations?

  11. I’ve learn some good stuff here. Certainly worth bookmarking for revisiting.
    I surprise how much effort you place to create
    any such fantastic informative site.

  12. Undeniably believe that which you stated. Your favorite justification seemed to be on the internet the
    simplest thing to be aware of. I say to you, I definitely get annoyed while people
    think about worries that they plainly don’t know about. You
    managed to hit the nail upon the top and also defined out the whole thing without having side-effects , people can take a signal.
    Will likely be back to get more. Thanks

  13. Just want to say your article is as astounding.
    The clearness in your post is just excellent and i can assume you’re
    an expert on this subject. Well with your permission allow me to grab your feed to keep
    updated with forthcoming post. Thanks a million and please keep up
    the enjoyable work.

  14. obviously like your web site but you have to take a look
    at the spelling on several of your posts. A number of them
    are rife with spelling problems and I find it very bothersome to tell the truth nevertheless I will definitely
    come again again.

  15. I think what you posted made a lot of sense.
    But, think on this, suppose you added a little information? I mean, I don’t wish to tell you
    how to run your website, however what if you added something that makes people want more?
    I mean 【CodeChef GRAPHCNT】[May Challenge 2015] Counting on a directed graph – Qizy's Database is
    kinda plain. You should look at Yahoo’s home page and note how
    they write news titles to grab people to open the links. You
    might add a related video or a picture or two to get readers excited about what you’ve got to say.
    Just my opinion, it might bring your posts a little bit more interesting.

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

  17. hey there and thank you for your info – I have certainly picked up anything
    new from right here. I did however expertise
    several technical issues using this web site, as I experienced to
    reload the site many times previous to I could get it to load correctly.

    I had been wondering if your hosting is OK? Not that I’m complaining, but sluggish loading instances times will very frequently
    affect your placement in google and could damage your high quality score if ads
    and marketing with Adwords. Well I am adding this RSS to my e-mail and can look out for much more of your respective exciting content.
    Ensure that you update this again very soon.

  18. I do not know if it’s just me or if perhaps everyone else encountering problems with your blog.
    It appears as if some of the written text in your content
    are running off the screen. Can someone else please comment and let me know if this is happening
    to them as well? This may be a problem with my web browser because I’ve had
    this happen before. Many thanks

  19. Howdy! I know this is kind of off topic but I was wondering which blog platform are you using for
    this site? I’m getting tired of WordPress because I’ve had issues with hackers and I’m looking at options for another platform.

    I would be fantastic if you could point me in the direction of a good platform.

  20. Hello are using WordPress for your site platform? I’m new to the blog world but I’m trying to get started and set up my own. Do you require any
    html coding expertise to make your own blog? Any help would be greatly
    appreciated!

  21. Just desire to say your article is as astonishing. The clarity in your post is just excellent and i
    can assume you are an expert on this subject.
    Well with your permission let me to grab your feed to keep
    updated with forthcoming post. Thanks a million and please carry on the rewarding work.

  22. Link exchange is nothing else but it is only placing the other person’s website link on your page at
    suitable place and other person will also do same in favor of
    you.

  23. I don’t know if it’s just me or if perhaps
    everyone else encountering issues with your website. It looks like some of the written text on your content are running off the screen. Can someone else please comment and
    let me know if this is happening to them as well?
    This could be a problem with my browser because I’ve had this happen previously.
    Thank you

  24. Its like you read my mind! You seem to know a lot about this, like you wrote the book in it or something. I think that you can do with a few pics to drive the message home a little bit, but instead of that, this is excellent blog. A great read. I’ll definitely be back.

Leave a Reply

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