Submission #250396

#	Time	Username	Problem	Language	Result	Execution time	Memory
250396		eohomegrownapps	Parachute rings (IOI12_rings)	C++14	20 / 100	4046 ms	35960 KiB

rings

#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 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31