Submission #292611

#	Time	Username	Problem	Language	Result	Execution time	Memory
292611		Haunted_Cpp	Simurgh (IOI17_simurgh)	C++17	13 / 100	3095 ms	384 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

struct DisjointSet {
  vector<int> par, size;
  DisjointSet(int n) {
    par = size = vector<int>(n);
    for (int i = 0; i < n; i++) {
      par[i] = i;
      size[i] = 1;
    }
  }
  int root(int x) {
    if (x == par[x]) return x;
    return par[x] = root(par[x]);
  }
  void join(int a, int b) {
    a = root(a);
    b = root(b);
    if (a == b) return;
    if (size[a] < size[b]) swap(a, b);
    par[b] = a;
    size[a] += size[b];
  }
  bool is(int a, int b) {
    return root(a) == root(b);
  }
};

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
  const int m = v.size();
  const int t = n - 1;
  vector<int> perm;
  for (int i = 0; i < m - t; i++) {
    perm.emplace_back(0);
  }
  for (int i = 0; i < t; i++) {
    perm.emplace_back(1);
  }
  
  do {
    DisjointSet DSU(n);
    bool valid = true;
    vector<int> res;
    for (int i = 0; i < m; i++) {
      if (perm[i]) {
        res.emplace_back(i);
        const int st = u[i];
        const int et = v[i];
        if (DSU.is(st, et)) {
           valid = false;
           break;
        }
        DSU.join(st, et);
      }
    }
    int must = -1;
    for (int i = 0; i < m; i++) {
      if (perm[i]) {
        const int st = u[i];
        const int et = v[i];
        if (must == -1) {
          must = DSU.root(st);
        }
        if (DSU.root(st) != must || DSU.root(et) != must) {
          valid = false;
          break;
        }
      }
    }
    if (!valid) continue;
    int cnt = count_common_roads(res);
    if (cnt == t) {
      return res;
    }
  } while(next_permutation(perm.begin(), perm.end()));
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:34:15: warning: control reaches end of non-void function [-Wreturn-type]
   34 |   vector<int> perm;
      |               ^~~~

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