제출 #1191208

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191208		JelalTkm	Simurgh (IOI17_simurgh)	C++20	13 / 100	22 ms	328 KiB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

// #define int long long int

const int N = 10;
const int md = 1e9 + 7;
const int INF = 1e9;

class DisjointSets {

  private:
  vector<int> p;

  public:
    DisjointSets(int n) : p(n) {
      for (int i = 0; i < n; i++) { p[i] = i;}
    }

  int get(int u) {
    return p[u] = (u == p[u] ? u : get(p[u]));
  }

  void unite(int u, int v) {
    u = get(u);
    v = get(v);
    if (u == v) {
      return;
    }
    p[v] = u;
    return;
  }
  
};

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
  vector<pair<int, int>> a;
  for (int i = 0; i < (int) u.size(); i++)
    a.push_back({u[i], v[i]});

  vector<int> ans;

  function<void(int, DisjointSets, int, vector<int> )> dfs = [&] (int nd, DisjointSets dsu, int st, vector<int> v) {
    if (nd == n - 1) {
      if (count_common_roads(v) == (n - 1)) ans = v;
      return;
    } else {
      auto ds = dsu;
      for (int i = st; i < (int) a.size(); i++) {
        if (dsu.get(a[i].first) != dsu.get(a[i].second)) {
          dsu.unite(a[i].first, a[i].second);
          v.push_back(i);
          dfs(nd + 1, dsu, i + 1, v);
          v.pop_back();
          dsu = ds;
        }
      }
    }
  };
  DisjointSets dsu1(n + 1);
  dfs(0, dsu1, 0, {});

  return ans;
}

// int32_t main(int32_t argc, char *argv[]) {
//   ios::sync_with_stdio(false);
//   cin.tie(nullptr);

//   int T = 1;
//   // cin >> T;
//   while (T--) {
//     int n = 7;
//     vector<pair<int, int>> a;
//     for (int i = 1; i <= n; i++)
//       for (int j = i + 1; j <= n; j++) {
//         a.push_back({i, j});
//       }

//     vector<bool> visited((int) a.size() + 1);
//     int ans = 0;
//     function<void(int, DisjointSets, int)> dfs = [&] (int nd, DisjointSets dsu, int st) {
//       if (nd == n - 1) {
//         ans++;
//         return;
//       } else {
//         auto ds = dsu;
//         for (int i = st; i < (int) a.size(); i++) {
//           if (!visited[i] && dsu.get(a[i].first) != dsu.get(a[i].second)) {
//             visited[i] = 1;
//             dsu.unite(a[i].first, a[i].second);
//             dfs(nd + 1, dsu, i + 1);
//             dsu = ds;
//             visited[i] = 0;
//           }
//         }
//       }
//     };
//     DisjointSets dsu1(n + 1);
//     dfs(0, dsu1, 0);

//     cout << ans << '\n';
//   }

//   return 0;
// }

• Subtask 1: 13 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30