oj.uz

답안 #66454

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
66454 2018-08-10T15:34:49 Z aquablitz11 낙하산 고리들 (IOI12_rings) C++14
37 / 100
 1292 ms 96468 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();
    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 (cnt3 > 4 || cnt4 > 1) return 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;
    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:109:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (G[u].size() > mxdeg.first) {
         ~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 23 ms 24188 KB Output is correct
3 Correct 24 ms 24196 KB Output is correct
4 Correct 22 ms 24196 KB Output is correct
5 Correct 24 ms 24196 KB Output is correct
6 Correct 25 ms 24408 KB Output is correct
7 Correct 22 ms 24408 KB Output is correct
8 Correct 24 ms 24408 KB Output is correct
9 Correct 24 ms 24408 KB Output is correct
10 Correct 24 ms 24408 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 457 ms 46488 KB Output is correct
2 Correct 955 ms 58544 KB Output is correct
3 Correct 1181 ms 62764 KB Output is correct
4 Correct 1191 ms 67244 KB Output is correct
5 Correct 1171 ms 68316 KB Output is correct
6 Correct 1292 ms 96468 KB Output is correct
7 Correct 1120 ms 96468 KB Output is correct
8 Correct 1111 ms 96468 KB Output is correct
9 Correct 1197 ms 96468 KB Output is correct
10 Correct 835 ms 96468 KB Output is correct

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 23 ms 24188 KB Output is correct
3 Correct 24 ms 24196 KB Output is correct
4 Correct 22 ms 24196 KB Output is correct
5 Correct 24 ms 24196 KB Output is correct
6 Correct 25 ms 24408 KB Output is correct
7 Correct 22 ms 24408 KB Output is correct
8 Correct 24 ms 24408 KB Output is correct
9 Correct 24 ms 24408 KB Output is correct
10 Correct 24 ms 24408 KB Output is correct
11 Correct 23 ms 96468 KB Output is correct
12 Incorrect 28 ms 96468 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 23 ms 24188 KB Output is correct
3 Correct 24 ms 24196 KB Output is correct
4 Correct 22 ms 24196 KB Output is correct
5 Correct 24 ms 24196 KB Output is correct
6 Correct 25 ms 24408 KB Output is correct
7 Correct 22 ms 24408 KB Output is correct
8 Correct 24 ms 24408 KB Output is correct
9 Correct 24 ms 24408 KB Output is correct
10 Correct 24 ms 24408 KB Output is correct
11 Correct 23 ms 96468 KB Output is correct
12 Incorrect 28 ms 96468 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 23 ms 24188 KB Output is correct
3 Correct 24 ms 24196 KB Output is correct
4 Correct 22 ms 24196 KB Output is correct
5 Correct 24 ms 24196 KB Output is correct
6 Correct 25 ms 24408 KB Output is correct
7 Correct 22 ms 24408 KB Output is correct
8 Correct 24 ms 24408 KB Output is correct
9 Correct 24 ms 24408 KB Output is correct
10 Correct 24 ms 24408 KB Output is correct
11 Correct 457 ms 46488 KB Output is correct
12 Correct 955 ms 58544 KB Output is correct
13 Correct 1181 ms 62764 KB Output is correct
14 Correct 1191 ms 67244 KB Output is correct
15 Correct 1171 ms 68316 KB Output is correct
16 Correct 1292 ms 96468 KB Output is correct
17 Correct 1120 ms 96468 KB Output is correct
18 Correct 1111 ms 96468 KB Output is correct
19 Correct 1197 ms 96468 KB Output is correct
20 Correct 835 ms 96468 KB Output is correct
21 Correct 23 ms 96468 KB Output is correct
22 Incorrect 28 ms 96468 KB Output isn't correct
23 Halted 0 ms 0 KB -