Submission #541765

#	Time	Username	Problem	Language	Result	Execution time	Memory
541765		alextodoran	Parachute rings (IOI12_rings)	C++17	100 / 100	2519 ms	119312 KiB

rings

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int CHAINS = 1;
const int CYCLE = 2;
const int RANDOM = 3;
const int QUIT = 4;

struct DSU {
    vector <int> root;
    vector <int> dim;
    int ignore;
    int cycleLength;
    int findRoot (int u) {
        return (root[u] == u ? u : root[u] = findRoot(root[u]));
    }
    bool join (int u, int v) {
        if (u == ignore || v == ignore) {
            return false;
        }
        u = findRoot(u);
        v = findRoot(v);
        if (u != v) {
            root[u] = v;
            dim[v] += dim[u];
            return false;
        } else {
            cycleLength = dim[u];
            return true;
        }
    }
    DSU (int N, int _ignore = -1) {
        root.resize(N);
        dim.resize(N);
        iota(root.begin(), root.end(), 0);
        fill(dim.begin(), dim.end(), 1);
        ignore = _ignore;
        cycleLength = 0;
    }
    DSU () {}
};

int N;

vector <vector <int>> adj;

DSU graph;
vector <pair <int, DSU>> options;
int phase;

int cntBlack;
vector <int> adjBlack;
bool red;

vector <pair <int, int>> links;

void Init (int _N) {
    N = _N;
    adj.resize(N);
    adjBlack.resize(N);
    phase = CHAINS;
    graph = DSU(N);
}
int CountCritical () {
    if (phase == QUIT) {
        return 0;
    } else if (phase == CHAINS) {
        return N;
    } else if (phase == CYCLE) {
        return graph.cycleLength;
    } else if (phase == RANDOM) {
        int answer = 0;
        for (pair <int, DSU> &opt : options) {
            if (red == true && (int) adj[opt.first].size() <= 3) {
                continue;
            }
            if (adjBlack[opt.first] < cntBlack) {
                continue;
            }
            if (opt.second.cycleLength > 0) {
                continue;
            }
            answer++;
        }
        return answer;
    }
}
void Link (int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
    if ((int) adj[v].size() >= 3) {
        swap(u, v);
    }
    if (phase < RANDOM && (int) adj[u].size() >= 3) {
        phase = RANDOM;
        options.push_back(make_pair(u, DSU()));
        for (int v : adj[u]) {
            options.push_back(make_pair(v, DSU()));
        }
        for (pair <int, DSU> &opt : options) {
            opt.second = DSU(N, opt.first);
            for (pair <int, int> l : links) {
                opt.second.join(l.first, l.second);
            }
        }
    }
    links.push_back(make_pair(u, v));
    if (phase == CHAINS) {
        if (graph.join(u, v) == true) {
            phase = CYCLE;
        }
    } else if (phase == CYCLE) {
        if (graph.join(u, v) == true) {
            phase = QUIT;
        }
    } else {
        graph.join(u, v);
        for (pair <int, DSU> &opt : options) {
            opt.second.join(u, v);
        }
        if ((int) adj[u].size() == 3) {
            cntBlack++;
            adjBlack[u]++;
            for (int x : adj[u]) {
                adjBlack[x]++;
            }
        }
        if ((int) adj[v].size() == 3) {
            cntBlack++;
            adjBlack[v]++;
            for (int x : adj[v]) {
                adjBlack[x]++;
            }
        }
        if ((int) adj[u].size() == 4 || (int) adj[v].size() == 4) {
            if (red == true) {
                phase = QUIT;
            } else {
                red = true;
            }
        }
    }
}

Compilation message (stderr)

rings.cpp: In function 'int CountCritical()':
rings.cpp:98:1: warning: control reaches end of non-void function [-Wreturn-type]
   98 | }
      | ^
rings.cpp: In function 'void Link(int, int)':
rings.cpp:20:8: warning: '*((void*)&<anonymous> +48)' may be used uninitialized in this function [-Wmaybe-uninitialized]
   20 | struct DSU {
      |        ^~~
rings.cpp:20:8: warning: '*((void*)&<anonymous> +48)' may be used uninitialized in this function [-Wmaybe-uninitialized]
   20 | struct DSU {
      |        ^~~

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