oj.uz

Submission #412669

# Submission time Handle Problem Language Result Execution time Memory
412669 2021-05-27T10:17:44 Z A_D Parachute rings (IOI12_rings) C++14
20 / 100
 4000 ms 41484 KB 
#include <bits/stdc++.h>

using namespace std;

int n;
const int N=1e6+100;
bool vis[N];
vector<int> g[N];
int ret;
int siz(int u,int p){
    int ret=0;
    for(auto x:g[u]){
        if(x==p)continue;
        ret++;
    }
    return ret;
}
void dfs(int u,int p,int me)
{
    vis[u]=1;
//    cout<<" u "<<u<<" "<<siz(u,me)<<endl;
    if(siz(u,me)>2){
        ret=0;
    }
    for(auto x:g[u]){
  //      cout<<" x "<<x<<" "<<siz(x,me)<<" "<<vis[x]<<" "<<me<<" "<<p<<endl;
        if(x==p||x==me)continue;
        if(vis[x]){
            ret=0;
            return;
        }
        dfs(x,u,me);
    }
}
int ok(int u)
{
    memset(vis,0,sizeof(vis));
    vis[u]=1;
    ret=1;
    for(int i=0;i<n;i++){
        int sz=siz(i,u);
        if(vis[i]==0&&sz<=1){
            dfs(i,i,u);
        }
    }
    for(int i=0;i<n;i++){
        if(vis[i]==0){
            ret=0;
        }
    }
    return ret;
}

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

void Link(int a, int b){
    g[a].push_back(b);
    g[b].push_back(a);
}

int CountCritical() {
    int ans=0;
    for(int i=0;i<n;i++){
        ans+=ok(i);
    //    return ans;
    }
    return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24644 KB Output is correct
2 Correct 708 ms 24944 KB Output is correct
3 Correct 974 ms 25016 KB Output is correct
4 Correct 74 ms 24784 KB Output is correct
5 Correct 337 ms 24988 KB Output is correct
6 Correct 873 ms 25292 KB Output is correct
7 Correct 460 ms 24784 KB Output is correct
8 Correct 318 ms 24976 KB Output is correct
9 Correct 962 ms 25068 KB Output is correct
10 Correct 990 ms 25008 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4056 ms 41484 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24644 KB Output is correct
2 Correct 708 ms 24944 KB Output is correct
3 Correct 974 ms 25016 KB Output is correct
4 Correct 74 ms 24784 KB Output is correct
5 Correct 337 ms 24988 KB Output is correct
6 Correct 873 ms 25292 KB Output is correct
7 Correct 460 ms 24784 KB Output is correct
8 Correct 318 ms 24976 KB Output is correct
9 Correct 962 ms 25068 KB Output is correct
10 Correct 990 ms 25008 KB Output is correct
11 Execution timed out 4088 ms 24836 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24644 KB Output is correct
2 Correct 708 ms 24944 KB Output is correct
3 Correct 974 ms 25016 KB Output is correct
4 Correct 74 ms 24784 KB Output is correct
5 Correct 337 ms 24988 KB Output is correct
6 Correct 873 ms 25292 KB Output is correct
7 Correct 460 ms 24784 KB Output is correct
8 Correct 318 ms 24976 KB Output is correct
9 Correct 962 ms 25068 KB Output is correct
10 Correct 990 ms 25008 KB Output is correct
11 Execution timed out 4088 ms 24836 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24644 KB Output is correct
2 Correct 708 ms 24944 KB Output is correct
3 Correct 974 ms 25016 KB Output is correct
4 Correct 74 ms 24784 KB Output is correct
5 Correct 337 ms 24988 KB Output is correct
6 Correct 873 ms 25292 KB Output is correct
7 Correct 460 ms 24784 KB Output is correct
8 Correct 318 ms 24976 KB Output is correct
9 Correct 962 ms 25068 KB Output is correct
10 Correct 990 ms 25008 KB Output is correct
11 Execution timed out 4056 ms 41484 KB Time limit exceeded
12 Halted 0 ms 0 KB -