oj.uz

Submission #250396

# Submission time Handle Problem Language Result Execution time Memory
250396 2020-07-17T16:53:34 Z eohomegrownapps Parachute rings (IOI12_rings) C++14
20 / 100
 4000 ms 35960 KB 
#include <bits/stdc++.h>
using namespace std;

int n;

vector<vector<int>> adjlist;

void Init(int nv) {
    n=nv;
    adjlist.resize(n);
}

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

vector<bool> visited;

int ignored;

bool isLine(int node, int par){
    //cout<<node<<" "<<par<<'\n';
    if (visited[node]){
        return false;
    }
    visited[node]=true;
    vector<int> an;
    for (int i : adjlist[node]){
        if (i!=ignored){
            //cout<<i<<' ';
            an.push_back(i);
        } else {
            //cout<<"ignored "<<i<<'\n';
        }
    }//cout<<'\n';
    if (an.size()==2){
        //cout<<"two\n";
        if (an[0]==par){
            return isLine(an[1], node);
        } else if (an[1]==par){
            return isLine(an[0], node);
        } else {
            return false;
        }
    } else if (an.size()==1&&an[0]!=par){
        return isLine(an[0],node);
    } else if (an.size()<=1){
        return true;
    } else {
        return false;
    }
}

bool checkLinear(int node, int ig){
    ignored=ig;
    vector<int> an;
    for (int i : adjlist[node]){
        if (i!=ignored){
            an.push_back(i);
        }
    }
    if (an.size()==0){
        visited[node]=true;
        return true;
    } else if (an.size()==1){
        return isLine(node,-1);
    } else if (an.size()==2){
        visited[node]=true;
        return isLine(an[0],node)&&isLine(an[1],node);
    } else {
        visited[node]=true;
        return false;
    }
}

bool isCritical(int node){
    //cout<<"checking "<<node<<'\n';
    visited.assign(n,false);
    for (int i = 0; i<n; i++){
        if (i==node){continue;}
        if (!visited[i]){
            if (!checkLinear(i,node)){
                //cout<<i<<" not linear for "<<node<<'\n';
                return false;
            }
        }
    }
    return true;
}

int CountCritical() {
    int numcritical = 0;
    for (int i = 0; i<n; i++){
        if (isCritical(i)){
            numcritical++;
        }
    }
    return numcritical;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 526 ms 680 KB Output is correct
3 Correct 106 ms 640 KB Output is correct
4 Correct 46 ms 384 KB Output is correct
5 Correct 784 ms 804 KB Output is correct
6 Correct 2483 ms 1228 KB Output is correct
7 Correct 24 ms 512 KB Output is correct
8 Correct 308 ms 748 KB Output is correct
9 Correct 388 ms 896 KB Output is correct
10 Correct 283 ms 784 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 526 ms 680 KB Output is correct
3 Correct 106 ms 640 KB Output is correct
4 Correct 46 ms 384 KB Output is correct
5 Correct 784 ms 804 KB Output is correct
6 Correct 2483 ms 1228 KB Output is correct
7 Correct 24 ms 512 KB Output is correct
8 Correct 308 ms 748 KB Output is correct
9 Correct 388 ms 896 KB Output is correct
10 Correct 283 ms 784 KB Output is correct
11 Execution timed out 4042 ms 864 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 526 ms 680 KB Output is correct
3 Correct 106 ms 640 KB Output is correct
4 Correct 46 ms 384 KB Output is correct
5 Correct 784 ms 804 KB Output is correct
6 Correct 2483 ms 1228 KB Output is correct
7 Correct 24 ms 512 KB Output is correct
8 Correct 308 ms 748 KB Output is correct
9 Correct 388 ms 896 KB Output is correct
10 Correct 283 ms 784 KB Output is correct
11 Execution timed out 4042 ms 864 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 526 ms 680 KB Output is correct
3 Correct 106 ms 640 KB Output is correct
4 Correct 46 ms 384 KB Output is correct
5 Correct 784 ms 804 KB Output is correct
6 Correct 2483 ms 1228 KB Output is correct
7 Correct 24 ms 512 KB Output is correct
8 Correct 308 ms 748 KB Output is correct
9 Correct 388 ms 896 KB Output is correct
10 Correct 283 ms 784 KB Output is correct
11 Execution timed out 4046 ms 35960 KB Time limit exceeded
12 Halted 0 ms 0 KB -