oj.uz

Submission #883110

# Submission time Handle Problem Language Result Execution time Memory
883110 2023-12-04T14:45:13 Z AkibAzmain Connecting Supertrees (IOI20_supertrees) C++17
11 / 100
 154 ms 23944 KB 
#include <bits/stdc++.h>
using namespace std;
#include "supertrees.h"
#include <vector>

int construct(std::vector<std::vector<int>> p) {
  int n = p.size();
  std::vector<std::vector<int>> ans (n, vector < int > (n));
  vector < array < bool, 4 > > pt (n);
  vector < pair < int, int > > dsu (n);
  for (int i = 0; i < n; ++i) dsu[i].first = -1, dsu[i].second = 1;
  for (int i = 0; i < n; ++i)
    for (int j = i + 1; j < n; ++j)
      if (p[i][j])
        {
          pt[i][p[i][j]] = true;
          pt[j][p[i][j]] = true;
          int ci = i, cj = j;
          while (dsu[ci].first != -1) ci = dsu[ci].first;
          while (dsu[cj].first != -1) cj = dsu[cj].first;
          if (ci != cj)
            {
              if (dsu[ci].second < dsu[cj].second) swap (ci, cj);
              dsu[cj].first = ci;
              dsu[ci].second += dsu[cj].second;
            }
        }
  map < int, array < set < int >, 4 > > m;
  for (int i = 0; i < n; ++i)
    {
      int ci = i;
      while (dsu[ci].first != -1) ci = dsu[ci].first;
      for (int j = 0; j < 4; ++j) if (pt[i][j]) m[ci][j].insert (i);
    }
  for (auto &[xx, x] : m)
    {
      if (x[1].empty () && x[2].empty ()) continue;
      int p = -1;
      for (auto &y : x[1])
        {
          if (p >= 0) ans[p][y] = ans[y][p] = 1;
          p = y;
        }
      if (x[2].empty ()) continue;
      int pp = p;
      int c = 0;
      for (auto &y : x[2])
        {
          if (x[1].count (y)) continue;
          ++c;
          if (p >= 0) ans[p][y] = ans[y][p] = 1;
          p = y;
        }
      ans[p][pp] = ans[pp][p] = 1;
      if (c < 2) return 0;
    }
  build (ans);
  return 1;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 0 ms 436 KB Output is correct
6 Correct 6 ms 1372 KB Output is correct
7 Correct 154 ms 23944 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 0 ms 436 KB Output is correct
6 Correct 6 ms 1372 KB Output is correct
7 Correct 154 ms 23944 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 416 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 6 ms 1372 KB Output is correct
13 Correct 145 ms 23928 KB Output is correct
14 Incorrect 1 ms 348 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 432 KB Output is correct
4 Runtime error 1 ms 348 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 440 KB Output is correct
2 Runtime error 1 ms 348 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 0 ms 436 KB Output is correct
6 Correct 6 ms 1372 KB Output is correct
7 Correct 154 ms 23944 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 416 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 6 ms 1372 KB Output is correct
13 Correct 145 ms 23928 KB Output is correct
14 Incorrect 1 ms 348 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 0 ms 436 KB Output is correct
6 Correct 6 ms 1372 KB Output is correct
7 Correct 154 ms 23944 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 416 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 6 ms 1372 KB Output is correct
13 Correct 145 ms 23928 KB Output is correct
14 Incorrect 1 ms 348 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -