oj.uz

Submission #70915

# Submission time Handle Problem Language Result Execution time Memory
70915 2018-08-23T16:52:46 Z dmfr Collapse (JOI18_collapse) C++11
0 / 100
 154 ms 7248 KB 
#include "collapse.h"
#include <deque>
#include <set>
#include <algorithm>

#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;
    int Index;
    Collapse(){}
    Collapse(const int& Day_, const int& Town_, const int& Index_): Day(Day_), Town(Town_), Index(Index_){}
    bool operator<(const Collapse& obj)const{
        if(obj.Day != this->Day) return (this->Day  < obj.Day );
        else                     return (this->Town < obj.Town);
    }
};

vector<bool> IsVisited;

int solve(const vector< set<int> >& Adj, const Collapse& collapse){
    const int& N = Adj.size();

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



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

            }
            if(BelongsToOldComponent) --componentCounter;
        }
    }
    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
0 0 1
0 1 3
0 2 4
0 4 0
3 1
=> 3

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

6 5 1
0 0 3
0 1 2
0 1 3
0 1 4
0 4 5
4 3
=> 2

*/
    const int& C = T.size();
    const int& Q = W.size();
//    if(N*Q < 5000*5000*10){
        IsVisited = vector<bool>(N);


        ///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]==0, X[i], Y[i]);
        }
        ///CollapsesDqe
        deque<Collapse> CollapsesDqe(Q);
        for(int i = 0; i < Q; ++i)
            CollapsesDqe[i] = Collapse(W[i],P[i],i);
        sort(CollapsesDqe.begin(), CollapsesDqe.end());

        ///Adjacency lists
        vector< set<int> > Adj(N);
        ///Solutions
        vector<int> SolutionsVtr(Q);
        ///Processing
        Collapse currCollapse;
        int currSolution;
        for(int i = 0; i < C; ++i){

            if(CollapsesDqe.size() == 0) break;

            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 ));
            }
            while(CollapsesDqe.front().Day <= i){
                currCollapse = CollapsesDqe.front(); CollapsesDqe.pop_front();
                currSolution = solve(Adj, currCollapse);
                SolutionsVtr[currCollapse.Index] = currSolution;
    //            cout << "SOLUTION: " << currSolution << endl;
                if(CollapsesDqe.size() == 0) break;
            }
        }
        return SolutionsVtr;
//    }
    return vector<int>(0);

}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 632 KB Output is correct
2 Correct 7 ms 632 KB Output is correct
3 Incorrect 6 ms 632 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 3616 KB Output is correct
2 Correct 75 ms 3616 KB Output is correct
3 Incorrect 154 ms 7248 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 7248 KB Output is correct
2 Correct 81 ms 7248 KB Output is correct
3 Correct 97 ms 7248 KB Output is correct
4 Incorrect 87 ms 7248 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 632 KB Output is correct
2 Correct 7 ms 632 KB Output is correct
3 Incorrect 6 ms 632 KB Output isn't correct
4 Halted 0 ms 0 KB -