Блог пользователя natsukagami

Tight timing on Simple problem
Автор natsukagami, 9 лет назад, По-английски

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.)

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        → Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.)

    → Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

→ Ответить