oj.uz

Submission #66457

# Submission time Handle Problem Language Result Execution time Memory
66457 2018-08-10T15:57:43 Z aquablitz11 Parachute rings (IOI12_rings) C++14
55 / 100
 4000 ms 96344 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]);
}
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;
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 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();
    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);
    }
}
 
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 test(int u) {
    //fprintf(stderr, "test(%d)\n", u);
    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());
 
    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);
    E.emplace_back(u, v);
    if (m)
        build_dsu();
    else if (!must_skip(u) && !must_skip(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 if (mfcnt == 0) return n;
    }
    if (mfcnt > 0) return 0;
    if (mxdeg.first == 3) {
        int cnt = 0;
        if (test(mxdeg.second)) ++cnt;
        for (auto v : G[mxdeg.second])
            if (test(v)) ++cnt;
        return cnt;
    }
    return test(mxdeg.second) ? 1 : 0;
}

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 23804 KB Output is correct
2 Correct 24 ms 24052 KB Output is correct
3 Correct 25 ms 24276 KB Output is correct
4 Correct 24 ms 24276 KB Output is correct
5 Correct 23 ms 24276 KB Output is correct
6 Correct 24 ms 24496 KB Output is correct
7 Correct 22 ms 24496 KB Output is correct
8 Correct 24 ms 24496 KB Output is correct
9 Correct 27 ms 24496 KB Output is correct
10 Correct 24 ms 24496 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 46664 KB Output is correct
2 Correct 955 ms 58536 KB Output is correct
3 Correct 1223 ms 62648 KB Output is correct
4 Correct 1195 ms 67280 KB Output is correct
5 Correct 1221 ms 68520 KB Output is correct
6 Correct 1300 ms 96344 KB Output is correct
7 Correct 1106 ms 96344 KB Output is correct
8 Correct 1157 ms 96344 KB Output is correct
9 Correct 1319 ms 96344 KB Output is correct
10 Correct 879 ms 96344 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23804 KB Output is correct
2 Correct 24 ms 24052 KB Output is correct
3 Correct 25 ms 24276 KB Output is correct
4 Correct 24 ms 24276 KB Output is correct
5 Correct 23 ms 24276 KB Output is correct
6 Correct 24 ms 24496 KB Output is correct
7 Correct 22 ms 24496 KB Output is correct
8 Correct 24 ms 24496 KB Output is correct
9 Correct 27 ms 24496 KB Output is correct
10 Correct 24 ms 24496 KB Output is correct
11 Correct 25 ms 96344 KB Output is correct
12 Correct 30 ms 96344 KB Output is correct
13 Correct 29 ms 96344 KB Output is correct
14 Correct 35 ms 96344 KB Output is correct
15 Correct 28 ms 96344 KB Output is correct
16 Correct 29 ms 96344 KB Output is correct
17 Correct 27 ms 96344 KB Output is correct
18 Correct 38 ms 96344 KB Output is correct
19 Correct 29 ms 96344 KB Output is correct
20 Correct 34 ms 96344 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23804 KB Output is correct
2 Correct 24 ms 24052 KB Output is correct
3 Correct 25 ms 24276 KB Output is correct
4 Correct 24 ms 24276 KB Output is correct
5 Correct 23 ms 24276 KB Output is correct
6 Correct 24 ms 24496 KB Output is correct
7 Correct 22 ms 24496 KB Output is correct
8 Correct 24 ms 24496 KB Output is correct
9 Correct 27 ms 24496 KB Output is correct
10 Correct 24 ms 24496 KB Output is correct
11 Correct 25 ms 96344 KB Output is correct
12 Correct 30 ms 96344 KB Output is correct
13 Correct 29 ms 96344 KB Output is correct
14 Correct 35 ms 96344 KB Output is correct
15 Correct 28 ms 96344 KB Output is correct
16 Correct 29 ms 96344 KB Output is correct
17 Correct 27 ms 96344 KB Output is correct
18 Correct 38 ms 96344 KB Output is correct
19 Correct 29 ms 96344 KB Output is correct
20 Correct 34 ms 96344 KB Output is correct
21 Correct 44 ms 96344 KB Output is correct
22 Correct 56 ms 96344 KB Output is correct
23 Correct 66 ms 96344 KB Output is correct
24 Execution timed out 4011 ms 96344 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23804 KB Output is correct
2 Correct 24 ms 24052 KB Output is correct
3 Correct 25 ms 24276 KB Output is correct
4 Correct 24 ms 24276 KB Output is correct
5 Correct 23 ms 24276 KB Output is correct
6 Correct 24 ms 24496 KB Output is correct
7 Correct 22 ms 24496 KB Output is correct
8 Correct 24 ms 24496 KB Output is correct
9 Correct 27 ms 24496 KB Output is correct
10 Correct 24 ms 24496 KB Output is correct
11 Correct 463 ms 46664 KB Output is correct
12 Correct 955 ms 58536 KB Output is correct
13 Correct 1223 ms 62648 KB Output is correct
14 Correct 1195 ms 67280 KB Output is correct
15 Correct 1221 ms 68520 KB Output is correct
16 Correct 1300 ms 96344 KB Output is correct
17 Correct 1106 ms 96344 KB Output is correct
18 Correct 1157 ms 96344 KB Output is correct
19 Correct 1319 ms 96344 KB Output is correct
20 Correct 879 ms 96344 KB Output is correct
21 Correct 25 ms 96344 KB Output is correct
22 Correct 30 ms 96344 KB Output is correct
23 Correct 29 ms 96344 KB Output is correct
24 Correct 35 ms 96344 KB Output is correct
25 Correct 28 ms 96344 KB Output is correct
26 Correct 29 ms 96344 KB Output is correct
27 Correct 27 ms 96344 KB Output is correct
28 Correct 38 ms 96344 KB Output is correct
29 Correct 29 ms 96344 KB Output is correct
30 Correct 34 ms 96344 KB Output is correct
31 Correct 44 ms 96344 KB Output is correct
32 Correct 56 ms 96344 KB Output is correct
33 Correct 66 ms 96344 KB Output is correct
34 Execution timed out 4011 ms 96344 KB Time limit exceeded
35 Halted 0 ms 0 KB -