Submission #117862

#	Time	Username	Problem	Language	Result	Execution time	Memory
117862		IOrtroiii	Pipes (CEOI15_pipes)	C++14	60 / 100	1222 ms	23240 KiB

pipes

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10