oj.uz

Submission #596055

# Submission time Handle Problem Language Result Execution time Memory
596055 2022-07-14T09:46:59 Z BT21tata Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 82252 KB 
#include <bits/stdc++.h>
using namespace std;
int n;
bool used[10005];
vector<int>g[1000005];

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

void Link(int A, int B)
{
    g[A+1].push_back(B+1);
    g[B+1].push_back(A+1);
}

bool dfs(int v, int p, int d)
{
    //cout<<"ok  "<<v<<' '<<p<<' '<<d<<' ';
    used[v]=1;
    int cnt=0;
    bool f=1;
    for(int u : g[v])
    {
        if(u!=d)
        {
            cnt++;
            if(u!=p)
            {
                if(!used[u]) f&=dfs(u, v, d);
                else return 0;
            }
        }
    }
    //cout<<"cnt "<<cnt<<endl;
    if(cnt>2) return 0;
    return f;
}

int CountCritical()
{
    int ans=0;
    for(int i=1; i<=n; i++)
    {
        bool ok=1;
        memset(used, 0, sizeof(used));
        for(int j=1; j<=n; j++)
        {
            if(!used[j] and j!=i) ok&=dfs(j, 0, i);
        }
        ans+=ok;
        //cout<<i<<' '<<ok<<endl;
    }
    return ans;

}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 372 ms 23988 KB Output is correct
3 Correct 581 ms 24020 KB Output is correct
4 Correct 33 ms 23800 KB Output is correct
5 Correct 211 ms 24036 KB Output is correct
6 Correct 645 ms 24296 KB Output is correct
7 Correct 177 ms 23828 KB Output is correct
8 Correct 309 ms 24020 KB Output is correct
9 Correct 555 ms 24140 KB Output is correct
10 Correct 569 ms 24056 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 262 ms 82252 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 372 ms 23988 KB Output is correct
3 Correct 581 ms 24020 KB Output is correct
4 Correct 33 ms 23800 KB Output is correct
5 Correct 211 ms 24036 KB Output is correct
6 Correct 645 ms 24296 KB Output is correct
7 Correct 177 ms 23828 KB Output is correct
8 Correct 309 ms 24020 KB Output is correct
9 Correct 555 ms 24140 KB Output is correct
10 Correct 569 ms 24056 KB Output is correct
11 Execution timed out 4094 ms 23900 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 372 ms 23988 KB Output is correct
3 Correct 581 ms 24020 KB Output is correct
4 Correct 33 ms 23800 KB Output is correct
5 Correct 211 ms 24036 KB Output is correct
6 Correct 645 ms 24296 KB Output is correct
7 Correct 177 ms 23828 KB Output is correct
8 Correct 309 ms 24020 KB Output is correct
9 Correct 555 ms 24140 KB Output is correct
10 Correct 569 ms 24056 KB Output is correct
11 Execution timed out 4094 ms 23900 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 372 ms 23988 KB Output is correct
3 Correct 581 ms 24020 KB Output is correct
4 Correct 33 ms 23800 KB Output is correct
5 Correct 211 ms 24036 KB Output is correct
6 Correct 645 ms 24296 KB Output is correct
7 Correct 177 ms 23828 KB Output is correct
8 Correct 309 ms 24020 KB Output is correct
9 Correct 555 ms 24140 KB Output is correct
10 Correct 569 ms 24056 KB Output is correct
11 Runtime error 262 ms 82252 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -