oj.uz

Submission #117862

# Submission time Handle Problem Language Result Execution time Memory
117862 2019-06-17T09:06:30 Z IOrtroiii Pipes (CEOI15_pipes) C++14
60 / 100
 1222 ms 23240 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 100100;

int n, m;
vector< tuple<int, int, int> > edges;

struct Dsu {
   int p[N];
   void reset(int n) {
      for (int i = 1; i <= n; ++i) {
         p[i] = i;
      }
   }
   int getp(int u) {
      if (p[u] == u) {
         return u;
      } else {
         return p[u] = getp(p[u]);
      }
   }
   bool mrg(int u, int v) {
      u = getp(u);
      v = getp(v);
      if (u == v) {
         return false;
      } else {
         p[v] = u;
         return true;
      }
   }
} a[2];

vector<pair<int, int>> g[N];
int low[N], num[N], tt;

void dfs(int u, int pid) {
   num[u] = low[u] = ++tt;
   for (auto e : g[u]) {
      int v, id;
      tie(v, id) = e;
      if (id == pid) {
         continue;
      } else if (num[v]) {
         low[u] = min(low[u], num[v]);
      } else {
         dfs(v, id);
         low[u] = min(low[u], low[v]);
         if (low[v] > num[u]) {
            cout << u << ' ' << v << '\n';
         }
      }
   }
}

int main() {
   ios_base::sync_with_stdio(false);

   cin >> n >> m;
   a[0].reset(n);
   a[1].reset(n);
   for (int i = 1; i <= m; ++i) {
      int u, v;
      cin >> u >> v;
      if (a[0].mrg(u, v)) {
         edges.emplace_back(u, v, i);
      } else if (a[1].mrg(u, v)) {
         edges.emplace_back(u, v, i);
      }
   }
   for (auto e : edges) {
      int u, v, id;
      tie(u, v, id) = e;
      g[u].emplace_back(v, id);
      g[v].emplace_back(u, id);
   }
   for (int i = 1; i <= n; ++i) if (!num[i]) {
      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 9 ms 3460 KB Output is correct
2 Correct 8 ms 3264 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 7100 KB Output is correct
2 Correct 108 ms 6732 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 9076 KB Output is correct
2 Correct 198 ms 5588 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 10992 KB Output is correct
2 Correct 256 ms 7664 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 15632 KB Output is correct
2 Correct 366 ms 10212 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 691 ms 19936 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 830 ms 21116 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1068 ms 23240 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1222 ms 19656 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -