oj.uz

Submission #789983

# Submission time Handle Problem Language Result Execution time Memory
789983 2023-07-22T08:39:51 Z peteza Parachute rings (IOI12_rings) C++14
52 / 100
 4000 ms 73172 KB 
#include <bits/stdc++.h>
using namespace std;

int N;
int cluster = 0;

int h[1000005];
int par[1000005];
bool vis[1000005];
bool inited = 0;
int cans = 0;
int deg[1000005], cmx;
vector<int> adj[1000005];

struct dat {
    int ign = -1;
    int deg[1000005] = {}, par[1000005];
    bool cool = 1;
    int fpar(int x) {
        return x == par[x] ? x : par[x] = fpar(par[x]);
    }
    dat (int x) {
        ign = x; cool = 1;
        for(int i=0;i<N;i++) par[i] = i;
        for(int i=0;i<N;i++) {
            if(i == ign) continue;
            for(int e:adj[i]) {
                if(e != ign) {
                    deg[i]++;
                    int I = fpar(i), E = fpar(e);
                    if(i < e && I == E) cool = 0;
                    par[I] = E;
                };
            }
            if(deg[i] >= 3) {
                cool = 0;
                return ;
            }
        }
    }
    void upd(int a, int b) {
        if(a == ign || b == ign) return;
        deg[a]++; deg[b]++;
        if(deg[a] >= 3 || deg[b] >= 3) cool = 0;
        if(fpar(a) == fpar(b)) cool = 0;
        par[fpar(a)] = fpar(b);
    }
};

vector<dat> elig;

int mg(int x, int y) {
  if(h[x] < h[y]) return par[x] = y;
  if(h[x] == h[y]) h[x]++;
  return par[y] = x;
}

int fpar(int x) {
  return x == par[x] ? x : fpar(par[x]);
}

void Init(int N_) {
    cmx = 0;
  N = N_; cluster = inited = cans = 0;
  elig.clear();
  for(int i=0;i<=N;i++) adj[i].clear();
  for(int i=0;i<=N;i++) deg[i] = 0, h[i] = 0, par[i] = i;
}

void dfs(int a) {
    if(vis[a]) return ;
    vis[a] = 1;
    cans++;
    for(int e:adj[a]) dfs(e);
}

void Link(int A, int B) {
  if(cluster >= 2) return;
  adj[A].push_back(B); adj[B].push_back(A);
  ++deg[A]; ++deg[B];
  cmx = max(cmx, deg[A]);
  cmx = max(cmx, deg[B]);
  if(cmx >= 3) {
    //initialize
    if(!inited) {
        cans = 0;
        inited = 1;
        int todo = A;
        if(deg[B] == 3) todo = B;
        for(auto E:adj[todo])
            elig.emplace_back(dat(E));
        elig.emplace_back(dat(todo));
        for(auto &e:elig) cans += e.cool;
    } else {
        cans = 0;
        for(auto it = elig.begin(); it != elig.end(); it++) {
            auto &e = *it;
            if(!e.cool) continue;
            e.upd(A, B);
            if(!e.cool) continue;
            cans++;
        }
    }
    return;
  }

  int pA = fpar(A), pB = fpar(B);
  if(pA == pB) {
    cluster++;
    memset(vis, 0, sizeof vis);
    dfs(A);
  } else {
    int res = mg(pA, pB); 
  }
}

int CountCritical() {
  if(cluster >= 2) 
    return 0;
  if(inited) return cans;
  if(!cluster)
    return N;
  //cluster count is equal to 1
  return cans;
}

/*
7 13
-1
1 2
-1
0 5
-1
2 0
-1
3 2
-1
3 5
-1
4 3
-1
*/

Compilation message

rings.cpp: In function 'void Init(int)':
rings.cpp:64:35: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   64 |   N = N_; cluster = inited = cans = 0;
      |                              ~~~~~^~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:113:9: warning: unused variable 'res' [-Wunused-variable]
  113 |     int res = mg(pA, pB);
      |         ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31524 KB Output is correct
2 Correct 167 ms 70872 KB Output is correct
3 Correct 195 ms 70860 KB Output is correct
4 Correct 46 ms 32588 KB Output is correct
5 Correct 110 ms 32716 KB Output is correct
6 Correct 177 ms 32896 KB Output is correct
7 Correct 51 ms 70856 KB Output is correct
8 Correct 137 ms 32708 KB Output is correct
9 Correct 193 ms 70988 KB Output is correct
10 Correct 196 ms 70896 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4049 ms 41736 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31524 KB Output is correct
2 Correct 167 ms 70872 KB Output is correct
3 Correct 195 ms 70860 KB Output is correct
4 Correct 46 ms 32588 KB Output is correct
5 Correct 110 ms 32716 KB Output is correct
6 Correct 177 ms 32896 KB Output is correct
7 Correct 51 ms 70856 KB Output is correct
8 Correct 137 ms 32708 KB Output is correct
9 Correct 193 ms 70988 KB Output is correct
10 Correct 196 ms 70896 KB Output is correct
11 Correct 175 ms 70936 KB Output is correct
12 Correct 351 ms 72136 KB Output is correct
13 Correct 367 ms 71108 KB Output is correct
14 Correct 253 ms 70976 KB Output is correct
15 Correct 242 ms 71116 KB Output is correct
16 Correct 316 ms 33052 KB Output is correct
17 Correct 331 ms 71956 KB Output is correct
18 Correct 354 ms 71196 KB Output is correct
19 Correct 341 ms 33120 KB Output is correct
20 Correct 367 ms 71180 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31524 KB Output is correct
2 Correct 167 ms 70872 KB Output is correct
3 Correct 195 ms 70860 KB Output is correct
4 Correct 46 ms 32588 KB Output is correct
5 Correct 110 ms 32716 KB Output is correct
6 Correct 177 ms 32896 KB Output is correct
7 Correct 51 ms 70856 KB Output is correct
8 Correct 137 ms 32708 KB Output is correct
9 Correct 193 ms 70988 KB Output is correct
10 Correct 196 ms 70896 KB Output is correct
11 Correct 175 ms 70936 KB Output is correct
12 Correct 351 ms 72136 KB Output is correct
13 Correct 367 ms 71108 KB Output is correct
14 Correct 253 ms 70976 KB Output is correct
15 Correct 242 ms 71116 KB Output is correct
16 Correct 316 ms 33052 KB Output is correct
17 Correct 331 ms 71956 KB Output is correct
18 Correct 354 ms 71196 KB Output is correct
19 Correct 341 ms 33120 KB Output is correct
20 Correct 367 ms 71180 KB Output is correct
21 Correct 881 ms 33548 KB Output is correct
22 Correct 1359 ms 34736 KB Output is correct
23 Correct 1758 ms 35600 KB Output is correct
24 Correct 1896 ms 72132 KB Output is correct
25 Correct 296 ms 72132 KB Output is correct
26 Correct 2193 ms 72200 KB Output is correct
27 Correct 2794 ms 36968 KB Output is correct
28 Correct 2950 ms 73172 KB Output is correct
29 Correct 1064 ms 72388 KB Output is correct
30 Correct 3241 ms 38456 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31524 KB Output is correct
2 Correct 167 ms 70872 KB Output is correct
3 Correct 195 ms 70860 KB Output is correct
4 Correct 46 ms 32588 KB Output is correct
5 Correct 110 ms 32716 KB Output is correct
6 Correct 177 ms 32896 KB Output is correct
7 Correct 51 ms 70856 KB Output is correct
8 Correct 137 ms 32708 KB Output is correct
9 Correct 193 ms 70988 KB Output is correct
10 Correct 196 ms 70896 KB Output is correct
11 Execution timed out 4049 ms 41736 KB Time limit exceeded
12 Halted 0 ms 0 KB -