답안 #49522 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49522	2018-05-30T07:23:47 Z	ho94949	낙하산 고리들 (IOI12_rings)	C++17	100 / 100	2760 ms	120348 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);
                //if(datas[i].first.numcyc != 0 || datas[i].first.ovdeg)
                //    datas.erase(datas.begin()+i);
            }
    }
}

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	28 ms	31992 KB	Output is correct
2	Correct	69 ms	71700 KB	Output is correct
3	Correct	74 ms	71700 KB	Output is correct
4	Correct	32 ms	71700 KB	Output is correct
5	Correct	32 ms	71700 KB	Output is correct
6	Correct	32 ms	71700 KB	Output is correct
7	Correct	72 ms	71700 KB	Output is correct
8	Correct	33 ms	71700 KB	Output is correct
9	Correct	75 ms	71784 KB	Output is correct
10	Correct	85 ms	71824 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	492 ms	71824 KB	Output is correct
2	Correct	1808 ms	104620 KB	Output is correct
3	Correct	2760 ms	110268 KB	Output is correct
4	Correct	1490 ms	110268 KB	Output is correct
5	Correct	1446 ms	110268 KB	Output is correct
6	Correct	1420 ms	110268 KB	Output is correct
7	Correct	2466 ms	110268 KB	Output is correct
8	Correct	1965 ms	114044 KB	Output is correct
9	Correct	2059 ms	120348 KB	Output is correct
10	Correct	964 ms	120348 KB	Output is correct

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	31992 KB	Output is correct
2	Correct	69 ms	71700 KB	Output is correct
3	Correct	74 ms	71700 KB	Output is correct
4	Correct	32 ms	71700 KB	Output is correct
5	Correct	32 ms	71700 KB	Output is correct
6	Correct	32 ms	71700 KB	Output is correct
7	Correct	72 ms	71700 KB	Output is correct
8	Correct	33 ms	71700 KB	Output is correct
9	Correct	75 ms	71784 KB	Output is correct
10	Correct	85 ms	71824 KB	Output is correct
11	Correct	77 ms	120348 KB	Output is correct
12	Correct	79 ms	120348 KB	Output is correct
13	Correct	80 ms	120348 KB	Output is correct
14	Correct	99 ms	120348 KB	Output is correct
15	Correct	78 ms	120348 KB	Output is correct
16	Correct	37 ms	120348 KB	Output is correct
17	Correct	79 ms	120348 KB	Output is correct
18	Correct	81 ms	120348 KB	Output is correct
19	Correct	36 ms	120348 KB	Output is correct
20	Correct	81 ms	120348 KB	Output is correct

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	31992 KB	Output is correct
2	Correct	69 ms	71700 KB	Output is correct
3	Correct	74 ms	71700 KB	Output is correct
4	Correct	32 ms	71700 KB	Output is correct
5	Correct	32 ms	71700 KB	Output is correct
6	Correct	32 ms	71700 KB	Output is correct
7	Correct	72 ms	71700 KB	Output is correct
8	Correct	33 ms	71700 KB	Output is correct
9	Correct	75 ms	71784 KB	Output is correct
10	Correct	85 ms	71824 KB	Output is correct
11	Correct	77 ms	120348 KB	Output is correct
12	Correct	79 ms	120348 KB	Output is correct
13	Correct	80 ms	120348 KB	Output is correct
14	Correct	99 ms	120348 KB	Output is correct
15	Correct	78 ms	120348 KB	Output is correct
16	Correct	37 ms	120348 KB	Output is correct
17	Correct	79 ms	120348 KB	Output is correct
18	Correct	81 ms	120348 KB	Output is correct
19	Correct	36 ms	120348 KB	Output is correct
20	Correct	81 ms	120348 KB	Output is correct
21	Correct	54 ms	120348 KB	Output is correct
22	Correct	77 ms	120348 KB	Output is correct
23	Correct	80 ms	120348 KB	Output is correct
24	Correct	138 ms	120348 KB	Output is correct
25	Correct	93 ms	120348 KB	Output is correct
26	Correct	139 ms	120348 KB	Output is correct
27	Correct	87 ms	120348 KB	Output is correct
28	Correct	149 ms	120348 KB	Output is correct
29	Correct	119 ms	120348 KB	Output is correct
30	Correct	99 ms	120348 KB	Output is correct

Subtask #5
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	31992 KB	Output is correct
2	Correct	69 ms	71700 KB	Output is correct
3	Correct	74 ms	71700 KB	Output is correct
4	Correct	32 ms	71700 KB	Output is correct
5	Correct	32 ms	71700 KB	Output is correct
6	Correct	32 ms	71700 KB	Output is correct
7	Correct	72 ms	71700 KB	Output is correct
8	Correct	33 ms	71700 KB	Output is correct
9	Correct	75 ms	71784 KB	Output is correct
10	Correct	85 ms	71824 KB	Output is correct
11	Correct	492 ms	71824 KB	Output is correct
12	Correct	1808 ms	104620 KB	Output is correct
13	Correct	2760 ms	110268 KB	Output is correct
14	Correct	1490 ms	110268 KB	Output is correct
15	Correct	1446 ms	110268 KB	Output is correct
16	Correct	1420 ms	110268 KB	Output is correct
17	Correct	2466 ms	110268 KB	Output is correct
18	Correct	1965 ms	114044 KB	Output is correct
19	Correct	2059 ms	120348 KB	Output is correct
20	Correct	964 ms	120348 KB	Output is correct
21	Correct	77 ms	120348 KB	Output is correct
22	Correct	79 ms	120348 KB	Output is correct
23	Correct	80 ms	120348 KB	Output is correct
24	Correct	99 ms	120348 KB	Output is correct
25	Correct	78 ms	120348 KB	Output is correct
26	Correct	37 ms	120348 KB	Output is correct
27	Correct	79 ms	120348 KB	Output is correct
28	Correct	81 ms	120348 KB	Output is correct
29	Correct	36 ms	120348 KB	Output is correct
30	Correct	81 ms	120348 KB	Output is correct
31	Correct	54 ms	120348 KB	Output is correct
32	Correct	77 ms	120348 KB	Output is correct
33	Correct	80 ms	120348 KB	Output is correct
34	Correct	138 ms	120348 KB	Output is correct
35	Correct	93 ms	120348 KB	Output is correct
36	Correct	139 ms	120348 KB	Output is correct
37	Correct	87 ms	120348 KB	Output is correct
38	Correct	149 ms	120348 KB	Output is correct
39	Correct	119 ms	120348 KB	Output is correct
40	Correct	99 ms	120348 KB	Output is correct
41	Correct	295 ms	120348 KB	Output is correct
42	Correct	695 ms	120348 KB	Output is correct
43	Correct	450 ms	120348 KB	Output is correct
44	Correct	1144 ms	120348 KB	Output is correct
45	Correct	1502 ms	120348 KB	Output is correct
46	Correct	884 ms	120348 KB	Output is correct
47	Correct	1187 ms	120348 KB	Output is correct
48	Correct	808 ms	120348 KB	Output is correct
49	Correct	866 ms	120348 KB	Output is correct
50	Correct	917 ms	120348 KB	Output is correct
51	Correct	511 ms	120348 KB	Output is correct
52	Correct	1033 ms	120348 KB	Output is correct
53	Correct	852 ms	120348 KB	Output is correct
54	Correct	1901 ms	120348 KB	Output is correct
55	Correct	2114 ms	120348 KB	Output is correct

답안 #49522

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