oj.uz

Submission #61783

# Submission time Handle Problem Language Result Execution time Memory
61783 2018-07-26T16:55:14 Z theknife2001 Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 1324 KB 
#include <bits/stdc++.h>


using namespace std;
const int N=5005;
vector < int > vec[N];
int n;
bool visited[N];

void Init(int N_) {
  n = N_;

}

void Link(int A, int B) {
    vec[A].push_back(B);
    vec[B].push_back(A);
}

bool dfs(int u , int p , int black)
{
    visited[u]=1;
    bool q=0;
    int cnt=0;
    for(auto v:vec[u])
    {
        if(v==black||v==p)
            continue ;
        if(visited[v])
            return 1;
        cnt++;
        q|=dfs(v,u,black);
    }
    if(cnt>=2&&p!=-1)
        q=1;
    if(p==-1&&cnt>2)
        q=1;
    return q;
}

int CountCritical() {
    int ans=0;
    bool q;
    for(int i=0;i<n;i++)
    {
        q=0;
        memset(visited,0,sizeof visited);
        for(int j=0;j<n;j++)
        {
            if(visited[j]==0&&j!=i)
                q|=dfs(j,-1,i);
        }
        if(!q)
            ans++;
    }
    return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 515 ms 756 KB Output is correct
3 Correct 922 ms 920 KB Output is correct
4 Correct 19 ms 920 KB Output is correct
5 Correct 250 ms 920 KB Output is correct
6 Correct 1079 ms 1112 KB Output is correct
7 Correct 210 ms 1112 KB Output is correct
8 Correct 436 ms 1112 KB Output is correct
9 Correct 1049 ms 1112 KB Output is correct
10 Correct 925 ms 1112 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 515 ms 756 KB Output is correct
3 Correct 922 ms 920 KB Output is correct
4 Correct 19 ms 920 KB Output is correct
5 Correct 250 ms 920 KB Output is correct
6 Correct 1079 ms 1112 KB Output is correct
7 Correct 210 ms 1112 KB Output is correct
8 Correct 436 ms 1112 KB Output is correct
9 Correct 1049 ms 1112 KB Output is correct
10 Correct 925 ms 1112 KB Output is correct
11 Execution timed out 4035 ms 1324 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 515 ms 756 KB Output is correct
3 Correct 922 ms 920 KB Output is correct
4 Correct 19 ms 920 KB Output is correct
5 Correct 250 ms 920 KB Output is correct
6 Correct 1079 ms 1112 KB Output is correct
7 Correct 210 ms 1112 KB Output is correct
8 Correct 436 ms 1112 KB Output is correct
9 Correct 1049 ms 1112 KB Output is correct
10 Correct 925 ms 1112 KB Output is correct
11 Execution timed out 4035 ms 1324 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 515 ms 756 KB Output is correct
3 Correct 922 ms 920 KB Output is correct
4 Correct 19 ms 920 KB Output is correct
5 Correct 250 ms 920 KB Output is correct
6 Correct 1079 ms 1112 KB Output is correct
7 Correct 210 ms 1112 KB Output is correct
8 Correct 436 ms 1112 KB Output is correct
9 Correct 1049 ms 1112 KB Output is correct
10 Correct 925 ms 1112 KB Output is correct
11 Runtime error 3 ms 1112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -