oj.uz

Submission #258796

# Submission time Handle Problem Language Result Execution time Memory
258796 2020-08-06T14:56:49 Z SamAnd Parachute rings (IOI12_rings) C++17
55 / 100
 4000 ms 87404 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
const int N = 1000006;

int n;
vector<int> g[N];

int c[N];

int k;
void dfs(int x)
{
    c[x] = k;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (!c[h])
            dfs(h);
    }
}

bool cc[N];

bool stg(int r)
{
    for (int x = 1; x <= n; ++x)
    {
        if (x == r)
            continue;
        int q = 0;
        for (int i = 0; i < g[x].size(); ++i)
        {
            int h = g[x][i];
            if (h == r)
                continue;
            ++q;
        }
        if (q >= 3)
            return false;
    }

    memset(c, 0, sizeof c);
    k = 0;
    c[r] = -1;
    for (int x = 1; x <= n; ++x)
    {
        if (!c[x])
        {
            ++k;
            dfs(x);
        }
    }

    memset(cc, false, sizeof cc);
    for (int x = 1; x <= n; ++x)
    {
        if (x == r)
            continue;
        int q = 0;
        for (int i = 0; i < g[x].size(); ++i)
        {
            int h = g[x][i];
            if (h == r)
                continue;
            ++q;
        }
        if (q <= 1)
            cc[c[x]] = true;
    }
    for (int i = 1; i <= k; ++i)
    {
        if (cc[i] == false)
            return false;
    }
    return true;
}

int solv0()
{
    /*int ans = 0;
    for (int x = 1; x <= n; ++x)
    {
        if (stg(x))
            ++ans;
    }
    return ans;*/

    for (int x = 1; x <= n; ++x)
    {
        if (sz(g[x]) >= 4)
        {
            if (stg(x))
                return 1;
            return 0;
        }
    }
    for (int x = 1; x <= n; ++x)
    {
        if (sz(g[x]) == 3)
        {
            int ans = 0;
            if (stg(x))
                ++ans;
            for (int i = 0; i < g[x].size(); ++i)
            {
                int h = g[x][i];
                if (stg(h))
                    ++ans;
            }
            return ans;
        }
    }

    memset(c, 0, sizeof c);
    k = 0;
    for (int x = 1; x <= n; ++x)
    {
        if (!c[x])
        {
            ++k;
            dfs(x);
        }
    }

    memset(cc, false, sizeof cc);
    for (int x = 1; x <= n; ++x)
    {
        if (sz(g[x]) <= 1)
            cc[c[x]] = true;
    }

    int qf = 0;
    for (int i = 1; i <= k; ++i)
    {
        if (cc[i] == false)
            ++qf;
    }
    if (qf >= 2)
        return 0;
    if (qf == 1)
    {
        int ans = 0;
        for (int x = 1; x <= n; ++x)
        {
            if (cc[c[x]] == false)
                ++ans;
        }
        return ans;
    }
    return n;
}

void Init(int N_)
{
    n = N_;
}

void Link(int x, int y)
{
    ++x;
    ++y;
    g[x].push_back(y);
    g[y].push_back(x);
}

int CountCritical()
{
    return solv0();
}

Compilation message

rings.cpp: In function 'void dfs(int)':
rings.cpp:19:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
rings.cpp: In function 'bool stg(int)':
rings.cpp:36:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[x].size(); ++i)
                         ~~^~~~~~~~~~~~~
rings.cpp:65:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[x].size(); ++i)
                         ~~^~~~~~~~~~~~~
rings.cpp: In function 'int solv0()':
rings.cpp:109:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < g[x].size(); ++i)
                             ~~^~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28672 KB Output is correct
2 Correct 22 ms 28928 KB Output is correct
3 Correct 21 ms 28928 KB Output is correct
4 Correct 23 ms 28672 KB Output is correct
5 Correct 18 ms 28928 KB Output is correct
6 Correct 26 ms 29048 KB Output is correct
7 Correct 14 ms 23840 KB Output is correct
8 Correct 24 ms 28928 KB Output is correct
9 Correct 21 ms 28928 KB Output is correct
10 Correct 20 ms 28928 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 51952 KB Output is correct
2 Correct 1000 ms 64644 KB Output is correct
3 Correct 952 ms 63880 KB Output is correct
4 Correct 1258 ms 73772 KB Output is correct
5 Correct 1267 ms 74220 KB Output is correct
6 Correct 1283 ms 87404 KB Output is correct
7 Correct 820 ms 62752 KB Output is correct
8 Correct 1474 ms 70816 KB Output is correct
9 Correct 1282 ms 73756 KB Output is correct
10 Correct 932 ms 73516 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28672 KB Output is correct
2 Correct 22 ms 28928 KB Output is correct
3 Correct 21 ms 28928 KB Output is correct
4 Correct 23 ms 28672 KB Output is correct
5 Correct 18 ms 28928 KB Output is correct
6 Correct 26 ms 29048 KB Output is correct
7 Correct 14 ms 23840 KB Output is correct
8 Correct 24 ms 28928 KB Output is correct
9 Correct 21 ms 28928 KB Output is correct
10 Correct 20 ms 28928 KB Output is correct
11 Correct 60 ms 28920 KB Output is correct
12 Correct 73 ms 29176 KB Output is correct
13 Correct 117 ms 29176 KB Output is correct
14 Correct 70 ms 28928 KB Output is correct
15 Correct 94 ms 28920 KB Output is correct
16 Correct 80 ms 29176 KB Output is correct
17 Correct 24 ms 29184 KB Output is correct
18 Correct 26 ms 29184 KB Output is correct
19 Correct 76 ms 29176 KB Output is correct
20 Correct 98 ms 29176 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28672 KB Output is correct
2 Correct 22 ms 28928 KB Output is correct
3 Correct 21 ms 28928 KB Output is correct
4 Correct 23 ms 28672 KB Output is correct
5 Correct 18 ms 28928 KB Output is correct
6 Correct 26 ms 29048 KB Output is correct
7 Correct 14 ms 23840 KB Output is correct
8 Correct 24 ms 28928 KB Output is correct
9 Correct 21 ms 28928 KB Output is correct
10 Correct 20 ms 28928 KB Output is correct
11 Correct 60 ms 28920 KB Output is correct
12 Correct 73 ms 29176 KB Output is correct
13 Correct 117 ms 29176 KB Output is correct
14 Correct 70 ms 28928 KB Output is correct
15 Correct 94 ms 28920 KB Output is correct
16 Correct 80 ms 29176 KB Output is correct
17 Correct 24 ms 29184 KB Output is correct
18 Correct 26 ms 29184 KB Output is correct
19 Correct 76 ms 29176 KB Output is correct
20 Correct 98 ms 29176 KB Output is correct
21 Execution timed out 4077 ms 29168 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28672 KB Output is correct
2 Correct 22 ms 28928 KB Output is correct
3 Correct 21 ms 28928 KB Output is correct
4 Correct 23 ms 28672 KB Output is correct
5 Correct 18 ms 28928 KB Output is correct
6 Correct 26 ms 29048 KB Output is correct
7 Correct 14 ms 23840 KB Output is correct
8 Correct 24 ms 28928 KB Output is correct
9 Correct 21 ms 28928 KB Output is correct
10 Correct 20 ms 28928 KB Output is correct
11 Correct 530 ms 51952 KB Output is correct
12 Correct 1000 ms 64644 KB Output is correct
13 Correct 952 ms 63880 KB Output is correct
14 Correct 1258 ms 73772 KB Output is correct
15 Correct 1267 ms 74220 KB Output is correct
16 Correct 1283 ms 87404 KB Output is correct
17 Correct 820 ms 62752 KB Output is correct
18 Correct 1474 ms 70816 KB Output is correct
19 Correct 1282 ms 73756 KB Output is correct
20 Correct 932 ms 73516 KB Output is correct
21 Correct 60 ms 28920 KB Output is correct
22 Correct 73 ms 29176 KB Output is correct
23 Correct 117 ms 29176 KB Output is correct
24 Correct 70 ms 28928 KB Output is correct
25 Correct 94 ms 28920 KB Output is correct
26 Correct 80 ms 29176 KB Output is correct
27 Correct 24 ms 29184 KB Output is correct
28 Correct 26 ms 29184 KB Output is correct
29 Correct 76 ms 29176 KB Output is correct
30 Correct 98 ms 29176 KB Output is correct
31 Execution timed out 4077 ms 29168 KB Time limit exceeded
32 Halted 0 ms 0 KB -