oj.uz

Submission #1051482

# Submission time Handle Problem Language Result Execution time Memory
1051482 2024-08-10T07:21:50 Z abczz Parachute rings (IOI12_rings) C++17
37 / 100
 1411 ms 187932 KB 
#include <iostream>
#include <map>
#include <vector>
#define ll long long

using namespace std;

map <ll, ll> mp;
vector <ll> adj[1000000], V;
ll n, x, y, tot, P[1000000], cyc[1000000], deg[1000000];
ll dsu(ll u) {
  if (P[u] == u) return u;
  else return P[u] = dsu(P[u]);
}
void Init(int N_) {
  n = N_;
  tot = 0;
  mp.clear();
  for (int i=0; i<n; ++i) {
    adj[i].clear();
    P[i] = i;
    ++mp[i];
  }
}

bool dfs(ll u, ll p, ll x) {
  bool res = 0;
  for (auto v : adj[u]) {
    if (v != p) {
      if (v != x && V.empty()) res |= dfs(v, u, x);
      else {
        if (mp.count(u)) V.push_back(u);
        return 1;
      }
    }
  }
  if (res && mp.count(u)) V.push_back(u);
  return res;
}

void Link(int A, int B) {
  if (mp.empty()) return;
  ++deg[A], ++deg[B];
  adj[A].push_back(B);
  adj[B].push_back(A);
  x = dsu(A), y = dsu(B);
  if (x == y) {
    ++cyc[x];
    ++tot;
    if (cyc[x] == 1) {
      V.clear();
      dfs(A, -1, A);
      mp.clear();
      for (auto u : V) ++mp[u];
    }
  }
  else {
    P[x] = y;
    if (cyc[x] && cyc[y]) {
      mp.clear();
      return;
    }
    cyc[y] += cyc[x];
  }
  if (deg[A] > 3) {
    if (mp.count(A)) {
      mp.clear();
      ++mp[A];
    }
    else mp.clear();
  }
  else if (deg[A] == 3) {
    V.clear();
    if (mp.count(A)) V.push_back(A);
    for (auto v : adj[A]) {
      if (mp.count(v)) V.push_back(v);
    }
    mp.clear();
    for (auto u : V) ++mp[u];
  }
  if (deg[B] > 3) {
    if (mp.count(B)) {
      mp.clear();
      ++mp[B];
    }
    else mp.clear();
  }
  else if (deg[B] == 3) {
    V.clear();
    if (mp.count(B)) V.push_back(B);
    for (auto v : adj[B]) {
      if (mp.count(v)) V.push_back(v);
    }
    mp.clear();
    for (auto u : V) ++mp[u];
  }
  if (tot > 1) {
    V.clear();
    for (auto [x, y] : mp) {
      if (deg[x] >= 3) V.push_back(x);
    }
    mp.clear();
    for (auto u : V) ++mp[u];
  }
}

int CountCritical() {
  return mp.size();
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26716 KB Output is correct
2 Correct 5 ms 27228 KB Output is correct
3 Correct 8 ms 27228 KB Output is correct
4 Correct 4 ms 26716 KB Output is correct
5 Correct 5 ms 27228 KB Output is correct
6 Correct 6 ms 27484 KB Output is correct
7 Correct 7 ms 27084 KB Output is correct
8 Correct 5 ms 27228 KB Output is correct
9 Correct 5 ms 27268 KB Output is correct
10 Correct 5 ms 27272 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 94932 KB Output is correct
2 Correct 624 ms 120052 KB Output is correct
3 Correct 334 ms 122760 KB Output is correct
4 Correct 790 ms 154568 KB Output is correct
5 Correct 821 ms 156356 KB Output is correct
6 Correct 1411 ms 187932 KB Output is correct
7 Correct 340 ms 122544 KB Output is correct
8 Correct 710 ms 144980 KB Output is correct
9 Correct 780 ms 153556 KB Output is correct
10 Correct 611 ms 152424 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26716 KB Output is correct
2 Correct 5 ms 27228 KB Output is correct
3 Correct 8 ms 27228 KB Output is correct
4 Correct 4 ms 26716 KB Output is correct
5 Correct 5 ms 27228 KB Output is correct
6 Correct 6 ms 27484 KB Output is correct
7 Correct 7 ms 27084 KB Output is correct
8 Correct 5 ms 27228 KB Output is correct
9 Correct 5 ms 27268 KB Output is correct
10 Correct 5 ms 27272 KB Output is correct
11 Incorrect 6 ms 27228 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26716 KB Output is correct
2 Correct 5 ms 27228 KB Output is correct
3 Correct 8 ms 27228 KB Output is correct
4 Correct 4 ms 26716 KB Output is correct
5 Correct 5 ms 27228 KB Output is correct
6 Correct 6 ms 27484 KB Output is correct
7 Correct 7 ms 27084 KB Output is correct
8 Correct 5 ms 27228 KB Output is correct
9 Correct 5 ms 27268 KB Output is correct
10 Correct 5 ms 27272 KB Output is correct
11 Incorrect 6 ms 27228 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26716 KB Output is correct
2 Correct 5 ms 27228 KB Output is correct
3 Correct 8 ms 27228 KB Output is correct
4 Correct 4 ms 26716 KB Output is correct
5 Correct 5 ms 27228 KB Output is correct
6 Correct 6 ms 27484 KB Output is correct
7 Correct 7 ms 27084 KB Output is correct
8 Correct 5 ms 27228 KB Output is correct
9 Correct 5 ms 27268 KB Output is correct
10 Correct 5 ms 27272 KB Output is correct
11 Correct 311 ms 94932 KB Output is correct
12 Correct 624 ms 120052 KB Output is correct
13 Correct 334 ms 122760 KB Output is correct
14 Correct 790 ms 154568 KB Output is correct
15 Correct 821 ms 156356 KB Output is correct
16 Correct 1411 ms 187932 KB Output is correct
17 Correct 340 ms 122544 KB Output is correct
18 Correct 710 ms 144980 KB Output is correct
19 Correct 780 ms 153556 KB Output is correct
20 Correct 611 ms 152424 KB Output is correct
21 Incorrect 6 ms 27228 KB Output isn't correct
22 Halted 0 ms 0 KB -