Submission #66429

#	Time	Username	Problem	Language	Result	Execution time	Memory
66429		aquablitz11	Parachute rings (IOI12_rings)	C++14	0 / 100	2481 ms	67868 KiB

rings

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int N = 1e6+10;

// graph data

int n;
vector<pii> E, ES;
vector<int> G[N];

int dfs(int u, int p, int s, int t)
{
    if (u == t)
        return 1;
    for (auto v : G[u]) if (v != p && (u != s || v != t)) {
        int r = dfs(v, u, s, t);
        if (r) return r+1;
    }
    return 0;
}

// dsu with copying for experimentation

int par[N], mfcnt, firstcycle;
int root(int u) {
    if (par[u] == u) return u;
    return par[u] = root(par[u]);
}
bool merge(int u, int v) {
    fprintf(stderr, "merge(%d, %d)\n", u, v);
    u = root(u), v = root(v);
    if (u == v) {
        if (++mfcnt == 1)
            firstcycle = dfs(u, -1, u, v);
        return false;
    }
    par[u] = v;
    return true;
}
int _np[N], _nv[N], nmfcnt, tick;
int &np(int u) {
    if (_nv[u] != tick) {
        _np[u] = par[u];
        _nv[u] = tick;
    }
    return _np[u];
}
int nroot(int u) {
    if (np(u) == u) return u;
    return np(u) = nroot(np(u));
}
bool nmerge(int u, int v) {
    fprintf(stderr, "nmerge(%d, %d)\n", u, v);
    u = nroot(u), v = nroot(v);
    if (u == v) return ++nmfcnt, false;
    np(u) = v;
    return true;
}

// state control (degree freq. histogram)

int cntok, cnt3, cnt4;
pii mxdeg(0, -1);

void testmod(int a, int b) {
    if (a <= 2) --cntok;
    if (a == 3) --cnt3;
    if (a >= 4) --cnt4;
    if (b <= 2) ++cntok;
    if (b == 3) ++cnt3;
    if (b >= 4) ++cnt4;
}

// rebuild dsu with exceptions

bool must_skip(int u) {
    if (mxdeg.first < 3)
        return false;
    if (u == mxdeg.second)
        return true;
    if (mxdeg.first == 3) {
        for (auto v : G[mxdeg.second]) if (v == u)
            return true;
    }
    return false;
}

void build_dsu() {
    fprintf(stderr, "rebuild dsu!\n");
    ES.clear();
    for (int i = 0; i < n; ++i)
        par[i] = i;
    for (auto e : E) {
        int u = e.first, v = e.second;
        if (must_skip(u) || must_skip(v)) {
            ES.emplace_back(u, v);
            fprintf(stderr, "skip edge %d %d\n", u, v);
            continue;
        }
        merge(e.first, e.second);
    }
}

bool modify(int u) {
    testmod(G[u].size()-1, G[u].size());
    if (G[u].size() > mxdeg.first) {
        mxdeg = pii(G[u].size(), u);
        if (mxdeg.first == 3 || mxdeg.first == 4)
            return true;
    }
    return false;
}

// testing functions

bool test(int u) {
    fprintf(stderr, "test(%d)\n", u);
    testmod(G[u].size(), G[u].size()-1);
    for (auto v : G[u])
        testmod(G[v].size(), G[v].size()-1);

    ++tick;
    nmfcnt = mfcnt;
    bool ok = cnt3 == 0 && cnt4 == 0;
    if (ok) for (auto e : ES) {
        if (e.first == u || e.second == u) continue;
        if (!nmerge(e.first, e.second)) ok = false;
        if (!ok) break;
    }

    testmod(G[u].size()-1, G[u].size());
    for (auto v : G[u])
        testmod(G[v].size()-1, G[v].size());

    return ok;
}

// problem functions:
 
void Init(int n) {
    fprintf(stderr, "Init(%d)\n", n);
    ::n = n;
    build_dsu();
}
 
void Link(int u, int v) {
    fprintf(stderr, "Link(%d, %d)\n", u, v);
    G[u].push_back(v);
    G[v].push_back(u);
    bool m = modify(u) | modify(v);
    if (m) {
        E.emplace_back(u, v);
        build_dsu();
    } else if (!must_skip(u) && !must_skip(v)) {
        E.emplace_back(u, v);
        merge(u, v);
    } else {
        ES.emplace_back(u, v);
    }
}
 
int CountCritical() {
    fprintf(stderr, "CountCritical()\n");
    if (mxdeg.first <= 2) {
        if (mfcnt > 1) return 0;
        else if (mfcnt == 1) return firstcycle;
        else return n;
    }
    if (mxdeg.first == 3) {
        int cnt = 0;
        if (test(mxdeg.second)) ++cnt;
        for (auto v : G[mxdeg.second])
            if (test(v)) ++cnt;
        return cnt;
    }
    if (cnt4 > 1) return 0;
    return test(mxdeg.second) ? 1 : 0;
}

Compilation message (stderr)

rings.cpp: In function 'bool modify(int)':
rings.cpp:107:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (G[u].size() > mxdeg.first) {
         ~~~~~~~~~~~~^~~~~~~~~~~~~

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