oj.uz

Submission #224458

# Submission time Handle Problem Language Result Execution time Memory
224458 2020-04-18T00:08:46 Z rama_pang Simurgh (IOI17_simurgh) C++14
13 / 100
 25 ms 3704 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

class DisjointSet {
 private:
  vector<int> p;
  vector<int> sz;

 public:
  DisjointSet() {}
  DisjointSet(int n) {
    p.assign(n, 0);
    iota(begin(p), end(p), 0);
    sz.assign(n, 1);
  }

  int Find(int x) {
    return p[x] == x ? x : p[x] = Find(p[x]);
  }

  bool Unite(int x, int y) {
    x = Find(x), y = Find(y);
    if (x == y) return false;
    if (sz[x] > sz[y]) swap(x, y);
    p[x] = y;
    sz[y] += sz[x];
    return true;
  }

  bool SameSet(int x, int y) {
    return Find(x) == Find(y);
  }
};

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
  int m = u.size();
  vector<int> is_royal(m, -1); // undetermined: -1, not royal: 0, royal: 1

  DisjointSet dsu(n);
  vector<int> T; // Spanning Tree of G
  vector<vector<int>> Tadj(n);
  vector<int> Tpar(n, -1);
  vector<int> Tdepth(n, 0);

  vector<bool> inT(n, false);
  for (int i = 0; i < m; i++) {
    if (dsu.Unite(u[i], v[i])) {
      inT[i] = true;
      T.emplace_back(i);
      Tadj[u[i]].emplace_back(i);
      Tadj[v[i]].emplace_back(i);
    }
  }

  int Troyal = count_common_roads(T);

  function<void(int, int)> dfs = [&](int cur, int p) {
    for (auto e : Tadj[cur]) {
      int nxt = (u[e] == cur ? v[e] : u[e]);
      if (nxt != p) {
        Tpar[nxt] = e;
        Tdepth[nxt] = Tdepth[cur] + 1;
        dfs(nxt, cur);
      }
    }
  };

  function<void(int)> determine = [&](int edge) {
    function<int(vector<int> T_, int, int)> Query = 
        [&](vector<int> T_, int remove, int add) {
      replace(begin(T_), end(T_), remove, add);
      return count_common_roads(T_);
    };

    vector<int> C; // Cycle
    int a = u[edge], b = v[edge];

    // Get edges of T in the cycle 
    if (Tdepth[a] > Tdepth[b]) swap(a, b);
    while (Tdepth[b] > Tdepth[a]) {
      C.emplace_back(Tpar[b]);
      b = (u[Tpar[b]] == b ? v[Tpar[b]] : u[Tpar[b]]);
    }
    while (a != b) {
      C.emplace_back(Tpar[a]);
      C.emplace_back(Tpar[b]);
      a = (u[Tpar[a]] == a ? v[Tpar[a]] : u[Tpar[a]]);
      b = (u[Tpar[b]] == b ? v[Tpar[b]] : u[Tpar[b]]);
    }
    for (int e : C) assert(e != -1);
    // check if there is an already determined edge
    for (auto e : C) {
      if (is_royal[edge] == -1 && is_royal[e] != -1) { // there is an already determined edge
        int Nroyal = Query(T, e, edge);
        if (Nroyal == Troyal) {
          is_royal[edge] = is_royal[e];
        } else {
          is_royal[edge] = is_royal[e] ? 0 : 1;
        }
      }
    }

    // all edges are undetermined, check each of them
    if (is_royal[edge] == -1) {
      vector<int> same;
      for (auto e : C) {
        int Nroyal = Query(T, e, edge);
        if (Nroyal == Troyal) {
          same.emplace_back(e); 
        } else if (Nroyal < Troyal) { // e is a royal road while edge isn't
          is_royal[e] = 1;
          is_royal[edge] = 0;
          break;
        } else if (Nroyal > Troyal) { // e isn't a royal road while edge is
          is_royal[e] = 0;
          is_royal[edge] = 1;
          break;
        }
      } 

      if (is_royal[edge] == -1) { // royal roads will never form a cycle
        is_royal[edge] = 0;
      }

      // update edges which have the same royality as edge
      for (auto e : same) {
        is_royal[e] = is_royal[edge];
      }
    }

    // we have determined edge, now to determine other edges in the cycle
    for (auto e : C) {
      if (is_royal[e] == -1) {
        int Nroyal = Query(T, e, edge);
        if (Nroyal == Troyal) {
          is_royal[e] = is_royal[edge];
        } else {
          is_royal[e] = is_royal[edge] ? 0 : 1; 
        }
      }
    }

    // for (auto e : C) {
    //   dsu.Unite(u[e], v[e]);
    // }
  };

  dfs(0, -1);
  dsu = DisjointSet(n); // determine whether edges from u[i] and v[i] are all determined

  for (int i = 0; i < m; i++) {
    if (inT[i]) continue; // edge is in T
    if (dsu.SameSet(u[i], v[i])) continue; // all edges from u to v is already determined
    determine(i); // determine royalities of cycle from u[i] to v[i]
  }

  for (auto e : T) {
    if (is_royal[e] == -1) { // if it is not yet determined, that means e is a bridge
      is_royal[e] = 1;
    }
  }


  vector<vector<int>> adj(n);
  for (int i = 0; i < m; i++) {
    if (inT[i]) continue;
    adj[u[i]].emplace_back(i);
    adj[v[i]].emplace_back(i);
  }

  function<void(int)> find_royal = [&](int vertex) {
    function<int(vector<int> T, vector<int> E)> Query = 
        [&](vector<int> T_, vector<int> E) { // complete the golden set E with edges from T_
      DisjointSet d(n);
      for (auto e : E) {
        d.Unite(u[e], v[e]);
      }

      int royals_from_T = 0;
      for (auto e : T_) {
        if (d.Unite(u[e], v[e])) {
          royals_from_T += is_royal[e];
          E.emplace_back(e);
        }
      }

      return count_common_roads(E) - royals_from_T;
    };

    vector<int> adjacent;
    for (auto e : adj[vertex]) {
      // if (u[e] == vertex) {
        adjacent.emplace_back(e);
      // }
    }
    
    for (int e : adjacent) {
      if (is_royal[e] == -1) {
        is_royal[e] = Query(T, {e});
      }
    }
    return;

    int count_royals = Query(T, adjacent);
    for (int L = 0; count_royals > 0; count_royals--) {
      int lo = L;
      int hi = (int) adjacent.size() - 1;

      while (lo < hi) {
        int mid = (lo + hi) / 2;
        vector<int> E(begin(adjacent) + L, begin(adjacent) + mid + 1);
        if (Query(T, E) > 0) {
          hi = mid;
        } else {
          lo = mid + 1;
        }
      }

      is_royal[adjacent[lo]] = 1;
      L = lo + 1;
    }

    for (auto e : adjacent) {
      if (is_royal[e] == -1) {
        is_royal[e] = 0;
      }
    }
  };

  // we have determined all roads in T, determine the remaining royal roads with binary search
  for (int i = 0; i < n; i++) {
    find_royal(i);
  }

  vector<int> royal_roads;
  for (int i = 0; i < m; i++) {
    if (is_royal[i] == 1) {
      royal_roads.emplace_back(i);
    }
  }
  
  return royal_roads;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB correct
2 Correct 4 ms 256 KB correct
3 Correct 4 ms 384 KB correct
4 Correct 4 ms 256 KB correct
5 Correct 4 ms 256 KB correct
6 Correct 4 ms 384 KB correct
7 Correct 4 ms 384 KB correct
8 Correct 4 ms 256 KB correct
9 Correct 4 ms 384 KB correct
10 Correct 5 ms 256 KB correct
11 Correct 4 ms 256 KB correct
12 Correct 4 ms 256 KB correct
13 Correct 4 ms 256 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB correct
2 Correct 4 ms 256 KB correct
3 Correct 4 ms 384 KB correct
4 Correct 4 ms 256 KB correct
5 Correct 4 ms 256 KB correct
6 Correct 4 ms 384 KB correct
7 Correct 4 ms 384 KB correct
8 Correct 4 ms 256 KB correct
9 Correct 4 ms 384 KB correct
10 Correct 5 ms 256 KB correct
11 Correct 4 ms 256 KB correct
12 Correct 4 ms 256 KB correct
13 Correct 4 ms 256 KB correct
14 Incorrect 7 ms 384 KB WA in grader: NO
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB correct
2 Correct 4 ms 256 KB correct
3 Correct 4 ms 384 KB correct
4 Correct 4 ms 256 KB correct
5 Correct 4 ms 256 KB correct
6 Correct 4 ms 384 KB correct
7 Correct 4 ms 384 KB correct
8 Correct 4 ms 256 KB correct
9 Correct 4 ms 384 KB correct
10 Correct 5 ms 256 KB correct
11 Correct 4 ms 256 KB correct
12 Correct 4 ms 256 KB correct
13 Correct 4 ms 256 KB correct
14 Incorrect 7 ms 384 KB WA in grader: NO
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB correct
2 Correct 5 ms 384 KB correct
3 Runtime error 25 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB correct
2 Correct 4 ms 256 KB correct
3 Correct 4 ms 384 KB correct
4 Correct 4 ms 256 KB correct
5 Correct 4 ms 256 KB correct
6 Correct 4 ms 384 KB correct
7 Correct 4 ms 384 KB correct
8 Correct 4 ms 256 KB correct
9 Correct 4 ms 384 KB correct
10 Correct 5 ms 256 KB correct
11 Correct 4 ms 256 KB correct
12 Correct 4 ms 256 KB correct
13 Correct 4 ms 256 KB correct
14 Incorrect 7 ms 384 KB WA in grader: NO
15 Halted 0 ms 0 KB -