natsukagami's blog

Tight timing on Simple problem
By natsukagami, 10 years ago, In English

Today I was given a problem which gives you an undirected unwieghted graph with n vertexes and m edges. You have two queries, 1 u v requires you to output 0 if vertex u and v are not connected, and 1 otherwise; and 2 u v requires you to insert an edge between u and v. n ≤ 1000, m ≤ 2n, q ≤ 105. The problem is a simple dsu problem.

Since we all know that the timing was tight and the judge was not so powerful as Codeforces's, we tried to code dsu with all optimizations (path-compressing, prioritized joining). However my code here (http://ideone.com/JWWxfL) was judged 10/11 tests with the last one TLE, meanwhile the other one (http://ideone.com/B4ZJzu) (which seems to not code prioritized joining correctly) was judged AC.

In real time testing, it seems that my code was around 0.2s slower than the other one on that maximum testcase. Please tell me why.

(I do realize I have a variable setCount which decreases everytime I do the joining, however removing it doesn't improve my results.)

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In join you call find(i) and find(j) twice in the worst case. Change this and it should get AC.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I expect find(i) and find(j) should have O(1) complexity the second time it's called (because of path compressing)?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What do you use dsu for? Rank heuristic or parent?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        If dsu[i] < 0 then i is the root of a set and  - dsu[i] is the size of the set. Otherwise dsu[i] is the root of the set that contains i. It's a common style of coding that we usually follow.

        → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think you should remove the command ios_base::sync_with_stdio(false);.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How can the second code get accepted when vector <int> dsu(1005,-1); and the constraint is 105?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I'm sorry. My fault. The constraint was n ≤ 1000, m ≤ 2n, q ≤ 105

    (Do not downvote his comment please. He pointed out a mistake in my statement, and I corrected it by editing.)

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Is it ok to use scanf / printf while using ios_base::sync_with_stdio(0)?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is, as long as you don't mix cin with scanf or cout with printf

    → Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Interesting topic. You could try path halving instead of the simple path compression. The discussion here mentions that path halving helped.

The code for path halving is

while (q != id[q]) {
        id[q] = id[id[q]];
        q = id[q];
}

where intially we have id[q] = q, see also here for the code.

If that does not help, you could also try other union techniques such as union by rank with path halving , e.g. this presentation mentions that union by rank with path halving is better than union by rank with path compression.

→ Reply