답안 #66453 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66453	2018-08-10T15:28:53 Z	aquablitz11	낙하산 고리들 (IOI12_rings)	C++14	37 / 100	1495 ms	96352 KB

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);
    int u0 = u, v0 = v;
    u = root(u), v = root(v);
    if (u == v) {
        if (++mfcnt == 1)
            firstcycle = dfs(u0, -1, u0, v0);
        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(), 0);
    for (auto v : G[u])
        testmod(G[v].size(), G[v].size()-1);
 
    bool ok = cnt3 == 0 && cnt4 == 0;
    ++tick;
    nmfcnt = mfcnt;
    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;
    }
    if (nmfcnt > 0) ok = false;
 
    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 (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

rings.cpp: In function 'bool modify(int)':
rings.cpp:108: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	23 ms	23800 KB	Output is correct
2	Correct	25 ms	24188 KB	Output is correct
3	Correct	25 ms	24264 KB	Output is correct
4	Correct	22 ms	24264 KB	Output is correct
5	Correct	24 ms	24308 KB	Output is correct
6	Correct	25 ms	24452 KB	Output is correct
7	Correct	21 ms	24452 KB	Output is correct
8	Correct	24 ms	24452 KB	Output is correct
9	Correct	23 ms	24452 KB	Output is correct
10	Correct	29 ms	24452 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	470 ms	46516 KB	Output is correct
2	Correct	1048 ms	58564 KB	Output is correct
3	Correct	1262 ms	62828 KB	Output is correct
4	Correct	1174 ms	67252 KB	Output is correct
5	Correct	1270 ms	68656 KB	Output is correct
6	Correct	1495 ms	96352 KB	Output is correct
7	Correct	1289 ms	96352 KB	Output is correct
8	Correct	1140 ms	96352 KB	Output is correct
9	Correct	1280 ms	96352 KB	Output is correct
10	Correct	843 ms	96352 KB	Output is correct

Subtask #3
0 / 18.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	23800 KB	Output is correct
2	Correct	25 ms	24188 KB	Output is correct
3	Correct	25 ms	24264 KB	Output is correct
4	Correct	22 ms	24264 KB	Output is correct
5	Correct	24 ms	24308 KB	Output is correct
6	Correct	25 ms	24452 KB	Output is correct
7	Correct	21 ms	24452 KB	Output is correct
8	Correct	24 ms	24452 KB	Output is correct
9	Correct	23 ms	24452 KB	Output is correct
10	Correct	29 ms	24452 KB	Output is correct
11	Correct	470 ms	46516 KB	Output is correct
12	Correct	1048 ms	58564 KB	Output is correct
13	Correct	1262 ms	62828 KB	Output is correct
14	Correct	1174 ms	67252 KB	Output is correct
15	Correct	1270 ms	68656 KB	Output is correct
16	Correct	1495 ms	96352 KB	Output is correct
17	Correct	1289 ms	96352 KB	Output is correct
18	Correct	1140 ms	96352 KB	Output is correct
19	Correct	1280 ms	96352 KB	Output is correct
20	Correct	843 ms	96352 KB	Output is correct
21	Correct	25 ms	96352 KB	Output is correct
22	Incorrect	28 ms	96352 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

답안 #66453

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 17.0 / 17.0

Subtask #3 0 / 18.0

Subtask #4 0 / 14.0

Subtask #5 0 / 31.0

Subtask #1
20.0 / 20.0

Subtask #2
17.0 / 17.0

Subtask #3
0 / 18.0

Subtask #4
0 / 14.0

Subtask #5
0 / 31.0