Submission #570415

#	Time	Username	Problem	Language	Result	Execution time	Memory
570415		cheissmart	Parachute rings (IOI12_rings)	C++14	100 / 100	1323 ms	78984 KiB

rings

#include <bits/stdc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
 
const int INF = 1e9 + 7, N = 1e6 + 7;

struct Graph {
    int deg[N], cycle_cnt, cycle_sz;
    int p[N], sz[N];
    bool ok;
    void init(int n) {
        ok = true;
        for(int i = 0; i < n; i++)
            p[i] = i, sz[i] = 1;
    }
    int find(int u) {
        return p[u] == u ? u : p[u] = find(p[u]);
    }
    void unite(int u, int v) {
        u = find(u), v = find(v);
        assert(u != v);
        if(sz[u] > sz[v]) swap(u, v);
        p[u] = v;
        sz[v] += sz[u];
    }
    void add_edge(int u, int v) {
        deg[u]++, deg[v]++;
        if(deg[u] >= 3 || deg[v] >= 3) ok = false;
        if(find(u) == find(v)) {
            ok = false;
            cycle_cnt++;
            cycle_sz = sz[find(u)];
        } else {
            unite(u, v);
        }
    }
} G, g[4];

vi special;

int n;
V<pi> todo;
bool has4 = false;

void Init(int _n) {
    n = _n;
    G.init(n);
    for(int i = 0; i < 4; i++)
        g[i].init(n);
}
 
void add_edge(int u, int v) {
    for(int i = 0; i < 4; i++) {
        if(u != special[i] && v != special[i]) {
            g[i].add_edge(u, v);
        }
    }
}

void found4(int x) {
    has4 = true;
    special.PB(x);
    for(auto[u, v]:todo) if(u == x || v == x)
        special.PB(u ^ v ^ x);
    assert(SZ(special) == 4);
    for(auto[u, v]:todo)
        add_edge(u, v);
}

void Link(int u, int v) {
    if(!has4) {
        todo.EB(u, v);
        G.add_edge(u, v);
        if(G.deg[u] == 3) {
            found4(u);
            return;
        }
        if(G.deg[v] == 3) {
            found4(v);
            return;
        }
    } else {
        add_edge(u, v);
    }
}

int CountCritical() {
    if(!has4) {
        if(G.cycle_cnt == 0) return n;
        else if(G.cycle_cnt == 1) return G.cycle_sz;
        else return 0;
    }
    return g[0].ok + g[1].ok + g[2].ok + g[3].ok;
}

Compilation message (stderr)

rings.cpp: In function 'void found4(int)':
rings.cpp:76:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |     for(auto[u, v]:todo) if(u == x || v == x)
      |             ^
rings.cpp:79:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |     for(auto[u, v]:todo)
      |             ^

• Subtask 1: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 14 / 14
• Subtask 5: 31 / 31