oj.uz

Submission #70882

# Submission time Handle Problem Language Result Execution time Memory
70882 2018-08-23T15:25:20 Z dmfr Collapse (JOI18_collapse) C++11
0 / 100
 15000 ms 3704 KB 
#include "collapse.h"
#include <deque>
#include <set>

//#include <iostream>

using namespace std;

class Cable{
public:
    bool Build;
    int Left;
    int Right;
    Cable(){}
    Cable(const bool& Build_, const int& Left_, const int& Right_): Build(Build_), Left(Left_), Right(Right_){}
};
class Collapse{
public:
    int Day;
    int Town;
    Collapse(){}
    Collapse(const int& Day_, const int& Town_): Day(Day_), Town(Town_){}
};

int solve(const vector< set<int> >& Adj, const Collapse& collapse){
    const int& N = Adj.size();
    ///Adj_[]
    vector< set<int> > Adj_ = Adj;
    set<int>::iterator it;
    for(int i = 0; i < N; ++i){
        set<int>& currAdj = Adj_[i];
        it = currAdj.upper_bound(collapse.Town);
        if(i <= collapse.Town){
            currAdj.erase(it, currAdj.end());
        }else{
            currAdj.erase(currAdj.begin(), it);
        }
    }

//    cout << "Adj[]:" << endl;
//    for(int i = 0; i < N; ++i){
//        cout << "i= " << i <<  "; ";
//        for(const auto& it:Adj[i])
//            cout << it << " ";
//        cout << endl;
//    }cout << endl;
//
//    cout << "Adj_[]:" << endl;
//    for(int i = 0; i < N; ++i){
//        cout << "i= " << i <<  "; ";
//        for(const auto& it:Adj_[i])
//            cout << it << " ";
//        cout << endl;
//    }cout << endl;


    ///Propagate
    vector<bool> IsVisited(N, false);
    deque<int> AwaitingVisit;
    int componentCounter = 0;
    int curr;
    for(int i = 0; i < N; ++i){
        if(!IsVisited[i]){
            ///Não pertence a nenhuma componente descoberta ate agora
            ++componentCounter;
            ///Adicionar visinhos do 1º nodo descoberto
            IsVisited[i] = true;
            for(const auto& it:Adj_[i])
                if(!IsVisited[it])
                    AwaitingVisit.push_back(it);
            ///Processar nodos do mesmo componente
            while(!AwaitingVisit.empty()){
                curr = AwaitingVisit.front(); AwaitingVisit.pop_front();
                if(!IsVisited[curr]){
                    IsVisited[curr] = true;
                    for(const auto& it:Adj_[curr])
                        if(!IsVisited[it])
                            AwaitingVisit.push_back(it);
                }

            }
        }
    }
    if(componentCounter == 1) return 0;
    else                      return componentCounter;


}

vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P){

/*
5 4 1
1 0 1
1 1 3
1 2 4
1 4 0
3 1
=> 3

5 8 2
1 0 1
1 0 4
1 1 3
1 2 4
1 0 3
0 1 3
1 1 2
1 3 4
3 1
7 3
=> 3
=> 2
*/

    const int& C = T.size();
    const int& Q = W.size();
    ///CablesVtr
    vector<Cable> CablesVtr(C);
    for(int i = 0; i < C; ++i){
        if(X[i] > Y[i]) swap(X[i], Y[i]);
        CablesVtr[i] = Cable(T[i], X[i], Y[i]);
    }
    ///CollapsesDqe
    deque<Collapse> CollapsesDqe(Q);
    for(int i = 0; i < Q; ++i)
        CollapsesDqe[i] = Collapse(W[i],P[i]);
    ///Adjacency lists
    vector< set<int> > Adj(N);
    ///Solutions
    deque<int> SolutionsDqe;
    ///Processing
    Collapse currCollapse;
    int currSolution;
    for(int i = 0; i < C; ++i){
        const Cable& currCable = CablesVtr[i];
        set<int>& Adj_Left  = Adj[currCable.Left ];
        set<int>& Adj_Right = Adj[currCable.Right];
        if(currCable.Build){
            Adj_Left .insert(currCable.Right);
            Adj_Right.insert(currCable.Left );
        }else{
            Adj_Left .erase(Adj_Left .find(currCable.Right));
            Adj_Right.erase(Adj_Right.find(currCable.Left ));
        }
        if(CollapsesDqe.front().Day == i){
            currCollapse = CollapsesDqe.front(); CollapsesDqe.pop_front();
            currSolution = solve(Adj, currCollapse);
            SolutionsDqe.push_back(currSolution);
//            cout << "SOLUTION: " << currSolution << endl;
        }
    }
    vector<int> ret(SolutionsDqe.begin(), SolutionsDqe.end());

	return ret;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 35.0

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