oj.uz

Submission #790000

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

int N;
int cluster = 0;

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(){}
    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);
    }
};

dat elig[4];

int mg(int x, int y) {
  return par[y] = x;
}

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

void Init(int N_) {
    cmx = 0;
  N = N_; cluster = inited = cans = 0;
  for(int i=0;i<=N;i++) adj[i].clear();
  for(int i=0;i<=N;i++) deg[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;
        int celig = 0;
        for(auto E:adj[todo])
            elig[celig++] =dat(E);
        elig[celig++] = dat(todo);
        for(auto &e:elig) cans += e.cool;
    } else {
        cans = 0;
        for(auto i=0;i<4;i++) {
            auto &e = elig[i];
            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:62:35: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   62 |   N = N_; cluster = inited = cans = 0;
      |                              ~~~~~^~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:111:9: warning: unused variable 'res' [-Wunused-variable]
  111 |     int res = mg(pA, pB);
      |         ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47316 KB Output is correct
2 Correct 165 ms 63068 KB Output is correct
3 Correct 175 ms 63088 KB Output is correct
4 Correct 52 ms 48248 KB Output is correct
5 Correct 115 ms 48448 KB Output is correct
6 Correct 185 ms 48648 KB Output is correct
7 Correct 47 ms 62928 KB Output is correct
8 Correct 147 ms 48408 KB Output is correct
9 Correct 191 ms 63200 KB Output is correct
10 Correct 185 ms 63216 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47316 KB Output is correct
2 Correct 165 ms 63068 KB Output is correct
3 Correct 175 ms 63088 KB Output is correct
4 Correct 52 ms 48248 KB Output is correct
5 Correct 115 ms 48448 KB Output is correct
6 Correct 185 ms 48648 KB Output is correct
7 Correct 47 ms 62928 KB Output is correct
8 Correct 147 ms 48408 KB Output is correct
9 Correct 191 ms 63200 KB Output is correct
10 Correct 185 ms 63216 KB Output is correct
11 Correct 188 ms 63248 KB Output is correct
12 Correct 357 ms 64320 KB Output is correct
13 Correct 337 ms 63356 KB Output is correct
14 Correct 248 ms 63200 KB Output is correct
15 Correct 234 ms 63240 KB Output is correct
16 Correct 273 ms 48748 KB Output is correct
17 Correct 347 ms 64372 KB Output is correct
18 Correct 340 ms 63604 KB Output is correct
19 Correct 335 ms 48808 KB Output is correct
20 Correct 337 ms 63660 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47316 KB Output is correct
2 Correct 165 ms 63068 KB Output is correct
3 Correct 175 ms 63088 KB Output is correct
4 Correct 52 ms 48248 KB Output is correct
5 Correct 115 ms 48448 KB Output is correct
6 Correct 185 ms 48648 KB Output is correct
7 Correct 47 ms 62928 KB Output is correct
8 Correct 147 ms 48408 KB Output is correct
9 Correct 191 ms 63200 KB Output is correct
10 Correct 185 ms 63216 KB Output is correct
11 Correct 188 ms 63248 KB Output is correct
12 Correct 357 ms 64320 KB Output is correct
13 Correct 337 ms 63356 KB Output is correct
14 Correct 248 ms 63200 KB Output is correct
15 Correct 234 ms 63240 KB Output is correct
16 Correct 273 ms 48748 KB Output is correct
17 Correct 347 ms 64372 KB Output is correct
18 Correct 340 ms 63604 KB Output is correct
19 Correct 335 ms 48808 KB Output is correct
20 Correct 337 ms 63660 KB Output is correct
21 Correct 848 ms 49172 KB Output is correct
22 Correct 1354 ms 50124 KB Output is correct
23 Correct 1629 ms 50920 KB Output is correct
24 Correct 1602 ms 65992 KB Output is correct
25 Correct 247 ms 64244 KB Output is correct
26 Correct 2087 ms 66636 KB Output is correct
27 Correct 2689 ms 52256 KB Output is correct
28 Correct 2825 ms 68180 KB Output is correct
29 Correct 1031 ms 65876 KB Output is correct
30 Correct 3169 ms 53496 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47316 KB Output is correct
2 Correct 165 ms 63068 KB Output is correct
3 Correct 175 ms 63088 KB Output is correct
4 Correct 52 ms 48248 KB Output is correct
5 Correct 115 ms 48448 KB Output is correct
6 Correct 185 ms 48648 KB Output is correct
7 Correct 47 ms 62928 KB Output is correct
8 Correct 147 ms 48408 KB Output is correct
9 Correct 191 ms 63200 KB Output is correct
10 Correct 185 ms 63216 KB Output is correct
11 Execution timed out 4066 ms 56036 KB Time limit exceeded
12 Halted 0 ms 0 KB -