oj.uz

Submission #95118

# Submission time Handle Problem Language Result Execution time Memory
95118 2019-01-27T12:44:05 Z MrTEK Pipes (CEOI15_pipes) C++14
100 / 100
 1223 ms 13360 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

const int N = 1e5 + 5;

int n,m,u,v,t,tin[N],fup[N];
vector <int> ed[N];
bool vis[N];

class dsu { public:
  int dad[N];
  void init() {
    for (int i = 1 ; i <= n ; i++)
      dad[i] = i;
  }

  int find(int x) {
    if (x == dad[x])
      return x;
    return dad[x] = find(dad[x]);
  }

  bool merge(int x,int y) {
    int dx = find(x) , dy = find(y);
    if (dx == dy)
      return false;
    dad[dx] = dy;
    return true;
  }
}t1,t2;

void is_bridge(int x,int y) {
  int l = lower_bound(ed[x].begin(),ed[x].end(),y) - ed[x].begin();
  int r = upper_bound(ed[x].begin(),ed[x].end(),y) - ed[x].begin();
  if (r != l + 1)
    return;
  cout << x << " " << y << endl;
}

void dfs(int cur,int par) {
  vis[cur] = true;
  tin[cur] = fup[cur] = ++t;
  for (auto i : ed[cur]) {
    if (i == par)
      continue;
    if (vis[i])
      fup[cur] = min(fup[cur],tin[i]);
    else{
      dfs(i,cur);
      fup[cur] = min(fup[cur],fup[i]);
      if (fup[i] > tin[cur])
        is_bridge(cur,i);
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> n >> m;
  t1.init();
  t2.init();
  for (int i = 1 ; i <= m ; i++) {
    cin >> u >> v;
    if (t1.merge(u,v) || t2.merge(u,v)) {
      ed[u].push_back(v);
      ed[v].push_back(u);
    }
  }
  for (int i = 1 ; i <= n ; i++)
    sort(ed[i].begin(),ed[i].end());
  for (int i = 1 ; i <= n ; i++)
    if (vis[i] == false)
      dfs(i,-1);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3200 KB Output is correct
2 Correct 9 ms 3072 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 3052 KB Output is correct
2 Correct 96 ms 2944 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 3704 KB Output is correct
2 Correct 191 ms 3324 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 5176 KB Output is correct
2 Correct 251 ms 5124 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 10232 KB Output is correct
2 Correct 364 ms 7160 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 11228 KB Output is correct
2 Correct 583 ms 8892 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 942 ms 13344 KB Output is correct
2 Correct 879 ms 9092 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1128 ms 13360 KB Output is correct
2 Correct 1070 ms 9080 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1223 ms 12776 KB Output is correct
2 Correct 1136 ms 10312 KB Output is correct