답안 #49519 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49519	2018-05-30T07:19:18 Z	ho94949	낙하산 고리들 (IOI12_rings)	C++17	100 / 100	2620 ms	120520 KB

rings

#include<vector>
#include<algorithm>
using namespace std;

const int MAXN = 1010101;

struct UF
{
    int ufd[MAXN], N;
    UF(){}
    UF(int n): N(n)
    {
        for(int i=0; i<n; ++i) ufd[i] = i;
    }
    int Find(int a)
    {
        if(a==ufd[a]) return a;
        return ufd[a] = Find(ufd[a]);
    }
    bool Union(int a, int b)
    {
        a = Find(a); b = Find(b);
        if(a==b) return false;
        ufd[a] = b; return true;
    }
};
struct DAT
{
    UF uf; int deg[MAXN]; int N; int numcyc; int cyclen; bool ovdeg;
    DAT(){}
    DAT(int n): N(n), uf(n), numcyc(0), cyclen(0), ovdeg(0)
    {
        for(int i=0; i<N; ++i) deg[i] = 0;
    }
    void Add(int a, int b)
    {
        deg[a]++; deg[b]++;
        if(deg[a] >= 3 || deg[b] >= 3) ovdeg=true;
        if(!uf.Union(a, b))
            if((++numcyc)==1)
                for(int i=0; i<N; ++i)
                    if(uf.Find(i) == uf.Find(a))
                        ++cyclen;
    }
};
DAT global;
int N, M;
pair<int, int> EList[MAXN];
vector<int> conn[MAXN];
int deg[MAXN], ovdeg;
vector<pair<DAT, int> > datas;

void Init(int _N)
{
    N = _N; M = 0; ovdeg = 0;
    DAT d(N); global = d;
}

DAT makeDAT(int x)
{
    DAT d(N);
    for(int i=0; i<M; ++i)
        if(EList[i].first != x && EList[i].second != x)
            d.Add(EList[i].first, EList[i].second);
    return d;
}

void makeGraph()
{
    for(int i=0; i<N; ++i)
    {
        int cnt = (deg[i] >= 3)?1:0;
        for(auto x: conn[i])
            if(deg[x] == 3) ++cnt;
        if(cnt == ovdeg)
            datas.emplace_back(makeDAT(i), i);
    }
}

void Link(int A, int B)
{
    if(ovdeg && datas.size() == 0) return;
    EList[M++] = make_pair(A, B);
    deg[A]++; deg[B]++;
    conn[A].push_back(B);
    conn[B].push_back(A);
    
    int povdeg = ovdeg;
    if(deg[A] == 3) ovdeg++;
    if(deg[B] == 3) ovdeg++;
    if(povdeg == 0 && ovdeg != 0)
        makeGraph();
    else
    {
        if(ovdeg == 0)
            global.Add(A, B);
        else
            for(int i=0; i<datas.size(); ++i)
                if(A!=datas[i].second && B != datas[i].second)
                    datas[i].first.Add(A, B);
    }
}

int CountCritical()
{
    if(ovdeg == 0)
    {
        if(global.numcyc == 0) return N;
        if(global.numcyc == 1) return global.cyclen;
        return 0;
    }
    else
    {
        int cnt = 0;
        for(const auto& x: datas)
            if(x.first.numcyc==0 && !x.first.ovdeg) ++cnt;
        return cnt;
    }
}

Compilation message

rings.cpp: In constructor 'DAT::DAT(int)':
rings.cpp:29:31: warning: 'DAT::N' will be initialized after [-Wreorder]
     UF uf; int deg[MAXN]; int N; int numcyc; int cyclen; bool ovdeg;
                               ^
rings.cpp:29:8: warning:   'UF DAT::uf' [-Wreorder]
     UF uf; int deg[MAXN]; int N; int numcyc; int cyclen; bool ovdeg;
        ^~
rings.cpp:31:5: warning:   when initialized here [-Wreorder]
     DAT(int n): N(n), uf(n), numcyc(0), cyclen(0), ovdeg(0)
     ^~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:98:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0; i<datas.size(); ++i)
                          ~^~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	31992 KB	Output is correct
2	Correct	76 ms	71828 KB	Output is correct
3	Correct	75 ms	71828 KB	Output is correct
4	Correct	33 ms	71828 KB	Output is correct
5	Correct	33 ms	71828 KB	Output is correct
6	Correct	34 ms	71828 KB	Output is correct
7	Correct	73 ms	71828 KB	Output is correct
8	Correct	34 ms	71828 KB	Output is correct
9	Correct	79 ms	71888 KB	Output is correct
10	Correct	71 ms	72008 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	502 ms	72008 KB	Output is correct
2	Correct	1837 ms	104724 KB	Output is correct
3	Correct	2620 ms	110516 KB	Output is correct
4	Correct	1446 ms	110516 KB	Output is correct
5	Correct	1567 ms	110516 KB	Output is correct
6	Correct	1352 ms	110516 KB	Output is correct
7	Correct	2486 ms	110516 KB	Output is correct
8	Correct	1888 ms	114260 KB	Output is correct
9	Correct	1853 ms	120520 KB	Output is correct
10	Correct	896 ms	120520 KB	Output is correct

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	31992 KB	Output is correct
2	Correct	76 ms	71828 KB	Output is correct
3	Correct	75 ms	71828 KB	Output is correct
4	Correct	33 ms	71828 KB	Output is correct
5	Correct	33 ms	71828 KB	Output is correct
6	Correct	34 ms	71828 KB	Output is correct
7	Correct	73 ms	71828 KB	Output is correct
8	Correct	34 ms	71828 KB	Output is correct
9	Correct	79 ms	71888 KB	Output is correct
10	Correct	71 ms	72008 KB	Output is correct
11	Correct	74 ms	120520 KB	Output is correct
12	Correct	82 ms	120520 KB	Output is correct
13	Correct	77 ms	120520 KB	Output is correct
14	Correct	73 ms	120520 KB	Output is correct
15	Correct	80 ms	120520 KB	Output is correct
16	Correct	35 ms	120520 KB	Output is correct
17	Correct	75 ms	120520 KB	Output is correct
18	Correct	75 ms	120520 KB	Output is correct
19	Correct	34 ms	120520 KB	Output is correct
20	Correct	76 ms	120520 KB	Output is correct

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	31992 KB	Output is correct
2	Correct	76 ms	71828 KB	Output is correct
3	Correct	75 ms	71828 KB	Output is correct
4	Correct	33 ms	71828 KB	Output is correct
5	Correct	33 ms	71828 KB	Output is correct
6	Correct	34 ms	71828 KB	Output is correct
7	Correct	73 ms	71828 KB	Output is correct
8	Correct	34 ms	71828 KB	Output is correct
9	Correct	79 ms	71888 KB	Output is correct
10	Correct	71 ms	72008 KB	Output is correct
11	Correct	74 ms	120520 KB	Output is correct
12	Correct	82 ms	120520 KB	Output is correct
13	Correct	77 ms	120520 KB	Output is correct
14	Correct	73 ms	120520 KB	Output is correct
15	Correct	80 ms	120520 KB	Output is correct
16	Correct	35 ms	120520 KB	Output is correct
17	Correct	75 ms	120520 KB	Output is correct
18	Correct	75 ms	120520 KB	Output is correct
19	Correct	34 ms	120520 KB	Output is correct
20	Correct	76 ms	120520 KB	Output is correct
21	Correct	58 ms	120520 KB	Output is correct
22	Correct	67 ms	120520 KB	Output is correct
23	Correct	78 ms	120520 KB	Output is correct
24	Correct	137 ms	120520 KB	Output is correct
25	Correct	91 ms	120520 KB	Output is correct
26	Correct	130 ms	120520 KB	Output is correct
27	Correct	85 ms	120520 KB	Output is correct
28	Correct	138 ms	120520 KB	Output is correct
29	Correct	114 ms	120520 KB	Output is correct
30	Correct	95 ms	120520 KB	Output is correct

Subtask #5
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	31992 KB	Output is correct
2	Correct	76 ms	71828 KB	Output is correct
3	Correct	75 ms	71828 KB	Output is correct
4	Correct	33 ms	71828 KB	Output is correct
5	Correct	33 ms	71828 KB	Output is correct
6	Correct	34 ms	71828 KB	Output is correct
7	Correct	73 ms	71828 KB	Output is correct
8	Correct	34 ms	71828 KB	Output is correct
9	Correct	79 ms	71888 KB	Output is correct
10	Correct	71 ms	72008 KB	Output is correct
11	Correct	502 ms	72008 KB	Output is correct
12	Correct	1837 ms	104724 KB	Output is correct
13	Correct	2620 ms	110516 KB	Output is correct
14	Correct	1446 ms	110516 KB	Output is correct
15	Correct	1567 ms	110516 KB	Output is correct
16	Correct	1352 ms	110516 KB	Output is correct
17	Correct	2486 ms	110516 KB	Output is correct
18	Correct	1888 ms	114260 KB	Output is correct
19	Correct	1853 ms	120520 KB	Output is correct
20	Correct	896 ms	120520 KB	Output is correct
21	Correct	74 ms	120520 KB	Output is correct
22	Correct	82 ms	120520 KB	Output is correct
23	Correct	77 ms	120520 KB	Output is correct
24	Correct	73 ms	120520 KB	Output is correct
25	Correct	80 ms	120520 KB	Output is correct
26	Correct	35 ms	120520 KB	Output is correct
27	Correct	75 ms	120520 KB	Output is correct
28	Correct	75 ms	120520 KB	Output is correct
29	Correct	34 ms	120520 KB	Output is correct
30	Correct	76 ms	120520 KB	Output is correct
31	Correct	58 ms	120520 KB	Output is correct
32	Correct	67 ms	120520 KB	Output is correct
33	Correct	78 ms	120520 KB	Output is correct
34	Correct	137 ms	120520 KB	Output is correct
35	Correct	91 ms	120520 KB	Output is correct
36	Correct	130 ms	120520 KB	Output is correct
37	Correct	85 ms	120520 KB	Output is correct
38	Correct	138 ms	120520 KB	Output is correct
39	Correct	114 ms	120520 KB	Output is correct
40	Correct	95 ms	120520 KB	Output is correct
41	Correct	267 ms	120520 KB	Output is correct
42	Correct	698 ms	120520 KB	Output is correct
43	Correct	419 ms	120520 KB	Output is correct
44	Correct	1164 ms	120520 KB	Output is correct
45	Correct	1511 ms	120520 KB	Output is correct
46	Correct	869 ms	120520 KB	Output is correct
47	Correct	1139 ms	120520 KB	Output is correct
48	Correct	779 ms	120520 KB	Output is correct
49	Correct	830 ms	120520 KB	Output is correct
50	Correct	890 ms	120520 KB	Output is correct
51	Correct	487 ms	120520 KB	Output is correct
52	Correct	999 ms	120520 KB	Output is correct
53	Correct	792 ms	120520 KB	Output is correct
54	Correct	1573 ms	120520 KB	Output is correct
55	Correct	1841 ms	120520 KB	Output is correct

답안 #49519

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 17.0 / 17.0

Subtask #3 18.0 / 18.0

Subtask #4 14.0 / 14.0

Subtask #5 31.0 / 31.0

Subtask #1
20.0 / 20.0

Subtask #2
17.0 / 17.0

Subtask #3
18.0 / 18.0

Subtask #4
14.0 / 14.0

Subtask #5
31.0 / 31.0