oj.uz

Submission #752589

# Submission time Handle Problem Language Result Execution time Memory
752589 2023-06-03T09:20:46 Z marvinthang Parachute rings (IOI12_rings) C++17
100 / 100
 733 ms 60836 KB 
/*************************************
*    author: marvinthang             *
*    created: 03.06.2023 15:50:54    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

struct DisjointSet {
    
    int n, max_deg;
    int cycle;
    vector <int> lab, deg;

    DisjointSet(int _n = 0) {
        n = _n; max_deg = 0; cycle = -1;
        lab.assign(n, -1);
        deg.assign(n, 0);
    }

    int find(int u) {
        return lab[u] < 0 ? u : lab[u] = find(lab[u]);
    }

    bool join(int u, int v) {
        int a = ++deg[u], b = ++deg[v];
        maximize(max_deg, max(a, b));
        if (max_deg > 2) cycle = 0;
        u = find(u); v = find(v);
        if (u == v) {
            if (cycle == -1) cycle = -lab[u];
            else cycle = 0;
            return false;
        }
        if (lab[u] > lab[v]) swap(u, v);
        lab[u] += lab[v];
        lab[v] = u;
        return true;
    }
};

using DSU = DisjointSet;

// end of template

const int MAX = 1e6 + 6;

int N, del[5];
bool tran;
DSU dsu[5];
vector <pair <int, int>> edges;

void Init(int N_) {
    N = N_;
    REP(i, 5) dsu[i] = DSU(N);
}

void Link(int A, int B) {
    if (!tran) {
        edges.emplace_back(A, B);
        dsu[0].join(A, B);
        if (dsu[0].max_deg > 2) {
            REP(u, N) if (dsu[0].deg[u] > 2) {
                del[1] = u;
                int t = 1;
                for (auto [x, y]: edges) {
                    if (x == u) del[++t] = y;
                    if (y == u) del[++t] = x;
                }
                assert(t == 4);
                break;
            }
            FOR(i, 1, 5) {
                for (auto [u, v]: edges) if (u != del[i] && v != del[i]) dsu[i].join(u, v);
            }
            tran = true;
        }
    } else {
        FOR(i, 1, 5) if (A != del[i] && B != del[i]) dsu[i].join(A, B);
    }
}

int CountCritical() {
    if (!tran) return dsu[0].cycle == -1 ? N : dsu[0].cycle;
    int cnt = 0;
    FOR(i, 1, 5) cnt += dsu[i].cycle == -1;
    return cnt;
}

#ifdef LOCAL
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define inbuf_len 1 << 16
#define outbuf_len 1 << 16

void Init(int N);
int CountCritical();
void Link(int a, int b);

int main() {
    file("rings");
  int tmp;

  /* Set input and output buffering */
  char *inbuf, *outbuf;
  inbuf = (char*) malloc(inbuf_len * sizeof(char));
  outbuf = (char*) malloc(outbuf_len * sizeof(char));
  tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
  tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);

  int N, L;
  tmp = scanf("%d %d", &N, &L);
  assert(tmp == 2);
  Init(N);

  int i;
  for (i = 0; i < L; i++) {
    int A, B;
    tmp = scanf("%d", &A);
    if (A == -1) {
      int critical;
      critical = CountCritical();
      printf("%d\n", critical);
    } else {
      tmp = scanf("%d", &B);
      assert(tmp == 1);
      Link(A, B);
    }
  }

  return 0;

}
#endif

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 432 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 3 ms 596 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 31688 KB Output is correct
2 Correct 570 ms 44496 KB Output is correct
3 Correct 733 ms 52296 KB Output is correct
4 Correct 364 ms 60836 KB Output is correct
5 Correct 358 ms 60816 KB Output is correct
6 Correct 398 ms 59956 KB Output is correct
7 Correct 710 ms 51732 KB Output is correct
8 Correct 680 ms 54620 KB Output is correct
9 Correct 670 ms 59416 KB Output is correct
10 Correct 304 ms 59568 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 432 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 4 ms 980 KB Output is correct
13 Correct 3 ms 852 KB Output is correct
14 Correct 3 ms 724 KB Output is correct
15 Correct 3 ms 1136 KB Output is correct
16 Correct 3 ms 1108 KB Output is correct
17 Correct 4 ms 852 KB Output is correct
18 Correct 4 ms 1236 KB Output is correct
19 Correct 3 ms 1032 KB Output is correct
20 Correct 5 ms 852 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 432 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 4 ms 980 KB Output is correct
13 Correct 3 ms 852 KB Output is correct
14 Correct 3 ms 724 KB Output is correct
15 Correct 3 ms 1136 KB Output is correct
16 Correct 3 ms 1108 KB Output is correct
17 Correct 4 ms 852 KB Output is correct
18 Correct 4 ms 1236 KB Output is correct
19 Correct 3 ms 1032 KB Output is correct
20 Correct 5 ms 852 KB Output is correct
21 Correct 12 ms 3160 KB Output is correct
22 Correct 21 ms 4928 KB Output is correct
23 Correct 27 ms 5940 KB Output is correct
24 Correct 29 ms 4884 KB Output is correct
25 Correct 14 ms 4504 KB Output is correct
26 Correct 26 ms 5028 KB Output is correct
27 Correct 26 ms 5920 KB Output is correct
28 Correct 31 ms 4812 KB Output is correct
29 Correct 24 ms 5036 KB Output is correct
30 Correct 30 ms 6336 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 432 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 157 ms 31688 KB Output is correct
12 Correct 570 ms 44496 KB Output is correct
13 Correct 733 ms 52296 KB Output is correct
14 Correct 364 ms 60836 KB Output is correct
15 Correct 358 ms 60816 KB Output is correct
16 Correct 398 ms 59956 KB Output is correct
17 Correct 710 ms 51732 KB Output is correct
18 Correct 680 ms 54620 KB Output is correct
19 Correct 670 ms 59416 KB Output is correct
20 Correct 304 ms 59568 KB Output is correct
21 Correct 2 ms 596 KB Output is correct
22 Correct 4 ms 980 KB Output is correct
23 Correct 3 ms 852 KB Output is correct
24 Correct 3 ms 724 KB Output is correct
25 Correct 3 ms 1136 KB Output is correct
26 Correct 3 ms 1108 KB Output is correct
27 Correct 4 ms 852 KB Output is correct
28 Correct 4 ms 1236 KB Output is correct
29 Correct 3 ms 1032 KB Output is correct
30 Correct 5 ms 852 KB Output is correct
31 Correct 12 ms 3160 KB Output is correct
32 Correct 21 ms 4928 KB Output is correct
33 Correct 27 ms 5940 KB Output is correct
34 Correct 29 ms 4884 KB Output is correct
35 Correct 14 ms 4504 KB Output is correct
36 Correct 26 ms 5028 KB Output is correct
37 Correct 26 ms 5920 KB Output is correct
38 Correct 31 ms 4812 KB Output is correct
39 Correct 24 ms 5036 KB Output is correct
40 Correct 30 ms 6336 KB Output is correct
41 Correct 139 ms 27352 KB Output is correct
42 Correct 325 ms 44860 KB Output is correct
43 Correct 206 ms 41700 KB Output is correct
44 Correct 485 ms 48716 KB Output is correct
45 Correct 497 ms 49040 KB Output is correct
46 Correct 308 ms 51404 KB Output is correct
47 Correct 367 ms 52292 KB Output is correct
48 Correct 328 ms 47540 KB Output is correct
49 Correct 305 ms 57876 KB Output is correct
50 Correct 320 ms 56836 KB Output is correct
51 Correct 230 ms 36352 KB Output is correct
52 Correct 420 ms 39892 KB Output is correct
53 Correct 312 ms 46712 KB Output is correct
54 Correct 633 ms 47016 KB Output is correct
55 Correct 672 ms 47140 KB Output is correct