Submission #826917

#	Time	Username	Problem	Language	Result	Execution time	Memory
826917		peteza	Parachute rings (IOI12_rings)	C++14	52 / 100	4066 ms	68692 KiB

rings

#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 (stderr)

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 / 20
• Subtask 2: 0 / 17
• Subtask 3: 18 / 18
• Subtask 4: 14 / 14
• Subtask 5: 0 / 31