oj.uz

Submission #66464

# Submission time Handle Problem Language Result Execution time Memory
66464 2018-08-10T16:10:40 Z aquablitz11 Parachute rings (IOI12_rings) C++14
37 / 100
 1339 ms 96436 KB 
#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
 
bool ffc = true;
int par[N], mfcnt, firstcycle;
int root(int u) {
    if (par[u] == u) return u;
    return par[u] = root(par[u]);
}
inline bool merge(int u, int v) {
    //fprintf(stderr, "merge(%d, %d)\n", u, v);
    int u0 = u, v0 = v;
    u = root(u), v = root(v);
    if (u == v) {
        if (++mfcnt == 1 && ffc)
            firstcycle = dfs(u0, -1, u0, v0);
        return false;
    }
    par[u] = v;
    return true;
}
int _np[N], _nv[N], tick;
inline 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));
}
inline bool nmerge(int u, int v) {
    //fprintf(stderr, "nmerge(%d, %d)\n", u, v);
    u = nroot(u), v = nroot(v);
    if (u == v) return false;
    np(u) = v;
    return true;
}
 
// state control (degree freq. histogram)
 
int cntok, cnt3, cnt4;
pii mxdeg(0, -1);
 
inline 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
 
inline 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;
}
 
inline void build_dsu() {
    //fprintf(stderr, "rebuild dsu!\n");
    ES.clear();
    mfcnt = 0;
    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);
    }
}
 
inline 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) {
            ffc = false;
            return true;
        }
    }
    return false;
}
 
// testing functions
 
bool dead[N];
inline bool test(int u) {
    //fprintf(stderr, "test(%d)\n", u);
    if (dead[u]) return false;
    testmod(G[u].size(), 0);
    for (auto v : G[u])
        testmod(G[v].size(), G[v].size()-1);
 
    bool ok = cnt3 == 0 && cnt4 == 0;
    ++tick;
    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(0, G[u].size());
    for (auto v : G[u])
        testmod(G[v].size()-1, G[v].size());
 
    if (!ok) dead[u] = true;
    return ok;
}
 
// problem functions:

bool state4 = false;
 
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);
    if (state4 && (u == mxdeg.second || v == mxdeg.second))
        return;
    bool m = modify(u) | modify(v);
    E.emplace_back(u, v);
    if (m) {
        build_dsu();
        if (mxdeg.first == 4) {
            state4 = true;
            testmod(G[mxdeg.second].size(), 0);
            for (auto a : G[mxdeg.second])
                testmod(G[a].size()-1, G[a].size()-1);
        }
    } else if (!must_skip(u) && !must_skip(v)) {
        merge(u, v);
    } else {
        ES.emplace_back(u, v);
    }
}
 
int CountCritical() {
    //fprintf(stderr, "CountCritical()\n");
    if (state4)
        return cnt3 == 0 && cnt4 == 0 && mfcnt == 0;
    if (mxdeg.first <= 2) {
        if (mfcnt > 1) return 0;
        else if (mfcnt == 1) return firstcycle;
        else if (mfcnt == 0) return n;
    }
    if (mfcnt > 0) return 0;
    int cnt = 0;
    if (test(mxdeg.second)) ++cnt;
    if (mxdeg.first == 3) {
        for (auto v : G[mxdeg.second])
            if (test(v)) ++cnt;
    }
    return cnt;
}

Compilation message

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23928 KB Output is correct
2 Correct 23 ms 24052 KB Output is correct
3 Correct 23 ms 24276 KB Output is correct
4 Correct 22 ms 24276 KB Output is correct
5 Correct 23 ms 24296 KB Output is correct
6 Correct 24 ms 24492 KB Output is correct
7 Correct 22 ms 24492 KB Output is correct
8 Correct 24 ms 24492 KB Output is correct
9 Correct 25 ms 24492 KB Output is correct
10 Correct 24 ms 24492 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 46408 KB Output is correct
2 Correct 888 ms 58424 KB Output is correct
3 Correct 1177 ms 62664 KB Output is correct
4 Correct 1186 ms 67164 KB Output is correct
5 Correct 1150 ms 68272 KB Output is correct
6 Correct 1286 ms 96436 KB Output is correct
7 Correct 1135 ms 96436 KB Output is correct
8 Correct 1179 ms 96436 KB Output is correct
9 Correct 1339 ms 96436 KB Output is correct
10 Correct 893 ms 96436 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23928 KB Output is correct
2 Correct 23 ms 24052 KB Output is correct
3 Correct 23 ms 24276 KB Output is correct
4 Correct 22 ms 24276 KB Output is correct
5 Correct 23 ms 24296 KB Output is correct
6 Correct 24 ms 24492 KB Output is correct
7 Correct 22 ms 24492 KB Output is correct
8 Correct 24 ms 24492 KB Output is correct
9 Correct 25 ms 24492 KB Output is correct
10 Correct 24 ms 24492 KB Output is correct
11 Correct 24 ms 96436 KB Output is correct
12 Correct 26 ms 96436 KB Output is correct
13 Incorrect 27 ms 96436 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23928 KB Output is correct
2 Correct 23 ms 24052 KB Output is correct
3 Correct 23 ms 24276 KB Output is correct
4 Correct 22 ms 24276 KB Output is correct
5 Correct 23 ms 24296 KB Output is correct
6 Correct 24 ms 24492 KB Output is correct
7 Correct 22 ms 24492 KB Output is correct
8 Correct 24 ms 24492 KB Output is correct
9 Correct 25 ms 24492 KB Output is correct
10 Correct 24 ms 24492 KB Output is correct
11 Correct 24 ms 96436 KB Output is correct
12 Correct 26 ms 96436 KB Output is correct
13 Incorrect 27 ms 96436 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23928 KB Output is correct
2 Correct 23 ms 24052 KB Output is correct
3 Correct 23 ms 24276 KB Output is correct
4 Correct 22 ms 24276 KB Output is correct
5 Correct 23 ms 24296 KB Output is correct
6 Correct 24 ms 24492 KB Output is correct
7 Correct 22 ms 24492 KB Output is correct
8 Correct 24 ms 24492 KB Output is correct
9 Correct 25 ms 24492 KB Output is correct
10 Correct 24 ms 24492 KB Output is correct
11 Correct 425 ms 46408 KB Output is correct
12 Correct 888 ms 58424 KB Output is correct
13 Correct 1177 ms 62664 KB Output is correct
14 Correct 1186 ms 67164 KB Output is correct
15 Correct 1150 ms 68272 KB Output is correct
16 Correct 1286 ms 96436 KB Output is correct
17 Correct 1135 ms 96436 KB Output is correct
18 Correct 1179 ms 96436 KB Output is correct
19 Correct 1339 ms 96436 KB Output is correct
20 Correct 893 ms 96436 KB Output is correct
21 Correct 24 ms 96436 KB Output is correct
22 Correct 26 ms 96436 KB Output is correct
23 Incorrect 27 ms 96436 KB Output isn't correct
24 Halted 0 ms 0 KB -