oj.uz

Submission #826917

# Submission time Handle Problem Language Result Execution time Memory
826917 2023-08-16T06:39:01 Z peteza Parachute rings (IOI12_rings) C++14
52 / 100
 4000 ms 68692 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3, unroll-loops")
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:2:40: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
    2 | #pragma GCC optimize("O3, unroll-loops")
      |                                        ^
rings.cpp:19:19: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   19 |     int fpar(int x) {
      |                   ^
rings.cpp:22:9: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   22 |     dat(){}
      |         ^
rings.cpp:23:15: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   23 |     dat (int x) {
      |               ^
rings.cpp:42:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   42 |     void upd(int a, int b) {
      |                          ^
rings.cpp:53:20: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   53 | int mg(int x, int y) {
      |                    ^
rings.cpp:57:15: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   57 | int fpar(int x) {
      |               ^
rings.cpp:61:17: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   61 | void Init(int N_) {
      |                 ^
rings.cpp: In function 'void Init(int)':
rings.cpp:63:35: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   63 |   N = N_; cluster = inited = cans = 0;
      |                              ~~~~~^~~
rings.cpp: At global scope:
rings.cpp:68:15: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   68 | void dfs(int a) {
      |               ^
rings.cpp:75:23: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   75 | void Link(int A, int B) {
      |                       ^
rings.cpp: In function 'void Link(int, int)':
rings.cpp:112:9: warning: unused variable 'res' [-Wunused-variable]
  112 |     int res = mg(pA, pB);
      |         ^~~
rings.cpp: At global scope:
rings.cpp:116:19: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
  116 | int CountCritical() {
      |                   ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47316 KB Output is correct
2 Correct 163 ms 63100 KB Output is correct
3 Correct 190 ms 63100 KB Output is correct
4 Correct 51 ms 48332 KB Output is correct
5 Correct 114 ms 48356 KB Output is correct
6 Correct 184 ms 48568 KB Output is correct
7 Correct 43 ms 62980 KB Output is correct
8 Correct 143 ms 48388 KB Output is correct
9 Correct 188 ms 63104 KB Output is correct
10 Correct 189 ms 63184 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47316 KB Output is correct
2 Correct 163 ms 63100 KB Output is correct
3 Correct 190 ms 63100 KB Output is correct
4 Correct 51 ms 48332 KB Output is correct
5 Correct 114 ms 48356 KB Output is correct
6 Correct 184 ms 48568 KB Output is correct
7 Correct 43 ms 62980 KB Output is correct
8 Correct 143 ms 48388 KB Output is correct
9 Correct 188 ms 63104 KB Output is correct
10 Correct 189 ms 63184 KB Output is correct
11 Correct 190 ms 63204 KB Output is correct
12 Correct 335 ms 64392 KB Output is correct
13 Correct 299 ms 63384 KB Output is correct
14 Correct 243 ms 63292 KB Output is correct
15 Correct 213 ms 63320 KB Output is correct
16 Correct 308 ms 48808 KB Output is correct
17 Correct 342 ms 64424 KB Output is correct
18 Correct 357 ms 63564 KB Output is correct
19 Correct 301 ms 48744 KB Output is correct
20 Correct 355 ms 63432 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47316 KB Output is correct
2 Correct 163 ms 63100 KB Output is correct
3 Correct 190 ms 63100 KB Output is correct
4 Correct 51 ms 48332 KB Output is correct
5 Correct 114 ms 48356 KB Output is correct
6 Correct 184 ms 48568 KB Output is correct
7 Correct 43 ms 62980 KB Output is correct
8 Correct 143 ms 48388 KB Output is correct
9 Correct 188 ms 63104 KB Output is correct
10 Correct 189 ms 63184 KB Output is correct
11 Correct 190 ms 63204 KB Output is correct
12 Correct 335 ms 64392 KB Output is correct
13 Correct 299 ms 63384 KB Output is correct
14 Correct 243 ms 63292 KB Output is correct
15 Correct 213 ms 63320 KB Output is correct
16 Correct 308 ms 48808 KB Output is correct
17 Correct 342 ms 64424 KB Output is correct
18 Correct 357 ms 63564 KB Output is correct
19 Correct 301 ms 48744 KB Output is correct
20 Correct 355 ms 63432 KB Output is correct
21 Correct 859 ms 49124 KB Output is correct
22 Correct 1372 ms 50144 KB Output is correct
23 Correct 1645 ms 50916 KB Output is correct
24 Correct 1684 ms 65972 KB Output is correct
25 Correct 243 ms 64232 KB Output is correct
26 Correct 1980 ms 66816 KB Output is correct
27 Correct 2751 ms 52276 KB Output is correct
28 Correct 2983 ms 68692 KB Output is correct
29 Correct 1016 ms 66056 KB Output is correct
30 Correct 3134 ms 53860 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47316 KB Output is correct
2 Correct 163 ms 63100 KB Output is correct
3 Correct 190 ms 63100 KB Output is correct
4 Correct 51 ms 48332 KB Output is correct
5 Correct 114 ms 48356 KB Output is correct
6 Correct 184 ms 48568 KB Output is correct
7 Correct 43 ms 62980 KB Output is correct
8 Correct 143 ms 48388 KB Output is correct
9 Correct 188 ms 63104 KB Output is correct
10 Correct 189 ms 63184 KB Output is correct
11 Execution timed out 4066 ms 57196 KB Time limit exceeded
12 Halted 0 ms 0 KB -