Submission #261140

#	Time	Username	Problem	Language	Result	Execution time	Memory
261140		georgerapeanu	Parachute rings (IOI12_rings)	C++11	55 / 100	4059 ms	75096 KiB

rings

#pragma once

#include <vector>
#include <algorithm>
#include <cstdio>
#include <queue>

using namespace std;

const int NMAX = 1e6;

int n;

vector<int> graph[NMAX + 5];

int dfs(int nod,int tata,vector<int> &viz){
    viz[nod] = 1;
    
    int found = 0;

    for(auto it:graph[nod]){
        if(viz[it] == 2){
            found = 1;
        }
        if(it == tata){
            continue;
        }
        if(viz[it] == 0){
            if(dfs(it,nod,viz) == 0){
                return 0;
            }
        }
        else if(viz[it] == 1){
            return 0;
        }
    }

    if(graph[nod].size() - found > 2){
        return 0;
    }

    return 1;
}

bool is_chain(int nod,vector<int> &viz){
    queue<int> q;
    vector<int> nodes;
    q.push(nod);
    viz[nod] = 1;

    while(!q.empty()){
        int nod = q.front();
        nodes.push_back(nod);
        q.pop();
        for(auto it:graph[nod]){
            if(viz[it] == 0){
                q.push(it);
                viz[it] = 1;
            }
        }
    }

    bool ok = true;
    bool found = false;

    for(auto it:nodes){
        ok &= (graph[it].size() <= 2);
        found |= (graph[it].size() <= 1);
    }

    for(auto it:nodes){
        viz[it] = 0;
    }
    
    return ok & found;
}

int bfs(int nod,vector<int> &viz){
    queue<int> q;
    vector<int> nodes;
    q.push(nod);
    viz[nod] = 1;

    while(!q.empty()){
        int nod = q.front();
        nodes.push_back(nod);
        q.pop();
        for(auto it:graph[nod]){
            if(viz[it] == 0){
                q.push(it);
                viz[it] = 1;
            }
        }
    }

    vector<int> candidates = nodes;

    bool big2 = false;

    for(auto it:nodes){
        if(graph[it].size() > 3){
            bool found = false;
            for(auto it2:candidates){
                found |= (it == it2);
            }
            candidates = {};
            if(found){
                candidates.push_back(it);
            }
            big2 = true;
        }
        else if(graph[it].size() == 3){
            if(big2 == false){
                candidates = graph[it];
                candidates.push_back(it);
            }
            else{
                vector<int> tmp;
                for(auto it2:candidates){
                    if(it2 == it || find(graph[it].begin(),graph[it].end(),it2) != graph[it].end()){
                        tmp.push_back(it2);
                    }
                }
                candidates.swap(tmp);
            }
            big2 = true;
        }
    }

    if(big2 == false)return nodes.size();

    int ans = 0;


    for(auto it:candidates){
        for(auto it2:nodes){
            viz[it2] = 0;
        }
        viz[it] = 2;
        bool ok = true;
        for(auto it2:graph[it]){
            if(viz[it2] == 0){
                ok &= dfs(it2,it,viz);
            }
        }
        ans += ok;
    }
    for(auto it:nodes){
        viz[it] = 1;
    }
    return ans;
}

void Init(int N_) {
    n = N_;

}

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

int CountCritical() {

    vector<int> viz(n + 1,0);

    int ans = 0;
    
    vector<int> data;
    vector<int> nonchains;

    for(int i = 1;i <= n;i++){
        if(viz[i] == false){
            if(is_chain(i,viz) == 0){
                nonchains.push_back(data.size());
            }
            data.push_back(bfs(i,viz));
        }
    }

    if(nonchains.empty()){
        for(auto it:data){
            ans += it;
        }
    }
    else if(nonchains.size() == 1){
        ans = data[nonchains[0]];
    }

    return ans;

}

Compilation message (stderr)

rings.cpp:1:9: warning: #pragma once in main file
 #pragma once
         ^~~~

• Subtask 1: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31