oj.uz

Submission #292611

# Submission time Handle Problem Language Result Execution time Memory
292611 2020-09-07T10:48:51 Z Haunted_Cpp Simurgh (IOI17_simurgh) C++17
13 / 100
 3000 ms 384 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB correct
2 Correct 24 ms 384 KB correct
3 Correct 11 ms 256 KB correct
4 Correct 1 ms 256 KB correct
5 Correct 1 ms 256 KB correct
6 Correct 4 ms 256 KB correct
7 Correct 0 ms 256 KB correct
8 Correct 0 ms 256 KB correct
9 Correct 0 ms 256 KB correct
10 Correct 1 ms 256 KB correct
11 Correct 1 ms 256 KB correct
12 Correct 2 ms 256 KB correct
13 Correct 11 ms 256 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB correct
2 Correct 24 ms 384 KB correct
3 Correct 11 ms 256 KB correct
4 Correct 1 ms 256 KB correct
5 Correct 1 ms 256 KB correct
6 Correct 4 ms 256 KB correct
7 Correct 0 ms 256 KB correct
8 Correct 0 ms 256 KB correct
9 Correct 0 ms 256 KB correct
10 Correct 1 ms 256 KB correct
11 Correct 1 ms 256 KB correct
12 Correct 2 ms 256 KB correct
13 Correct 11 ms 256 KB correct
14 Execution timed out 3095 ms 384 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB correct
2 Correct 24 ms 384 KB correct
3 Correct 11 ms 256 KB correct
4 Correct 1 ms 256 KB correct
5 Correct 1 ms 256 KB correct
6 Correct 4 ms 256 KB correct
7 Correct 0 ms 256 KB correct
8 Correct 0 ms 256 KB correct
9 Correct 0 ms 256 KB correct
10 Correct 1 ms 256 KB correct
11 Correct 1 ms 256 KB correct
12 Correct 2 ms 256 KB correct
13 Correct 11 ms 256 KB correct
14 Execution timed out 3095 ms 384 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB correct
2 Incorrect 74 ms 376 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB correct
2 Correct 24 ms 384 KB correct
3 Correct 11 ms 256 KB correct
4 Correct 1 ms 256 KB correct
5 Correct 1 ms 256 KB correct
6 Correct 4 ms 256 KB correct
7 Correct 0 ms 256 KB correct
8 Correct 0 ms 256 KB correct
9 Correct 0 ms 256 KB correct
10 Correct 1 ms 256 KB correct
11 Correct 1 ms 256 KB correct
12 Correct 2 ms 256 KB correct
13 Correct 11 ms 256 KB correct
14 Execution timed out 3095 ms 384 KB Time limit exceeded
15 Halted 0 ms 0 KB -