oj.uz

Submission #70926

# Submission time Handle Problem Language Result Execution time Memory
70926 2018-08-23T17:36:50 Z dmfr Collapse (JOI18_collapse) C++11
5 / 100
 940 ms 7512 KB 
#include "collapse.h"
#include <deque>
#include <set>
#include <algorithm>

//#include <iostream>

using namespace std;

typedef pair<int,int> pii;

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();
    ///Propagate
    fill(IsVisited.begin(), IsVisited.end(), 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;
            if(i <= collapse.Town){
                for(auto it = Adj[i].begin(); it != Adj[i].end(); ++it){
                    if(collapse.Town < *it) break;
                    if(!IsVisited[*it])
                        AwaitingVisit.push_back(*it);
                }
            }else{
                for(auto it = Adj[i].rbegin(); it != Adj[i].rend(); ++it){
                    if(*it <= collapse.Town) break;
                    if(!IsVisited[*it])
                        AwaitingVisit.push_back(*it);
                }
            }
            ///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(auto it = Adj[curr].begin(); it != Adj[curr].end(); ++it){
                            if(collapse.Town < *it) break;
                            if(!IsVisited[*it])
                                AwaitingVisit.push_back(*it);
                        }
                    }else{
                        for(auto it = Adj[curr].rbegin(); it != Adj[curr].rend(); ++it){
                            if(*it <= collapse.Town) break;
                            if(!IsVisited[*it])
                                AwaitingVisit.push_back(*it);
                        }
                    }
                }

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


}

int solve2(const vector< set<int> >& Adj){
    const int& N = Adj.size();
    ///Propagate
    fill(IsVisited.begin(), IsVisited.end(), 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(auto it = Adj[i].rbegin(); it != Adj[i].rend(); ++it){
                if(!IsVisited[*it])
                    AwaitingVisit.push_back(*it);
            }
            ///Processar nodos do mesmo componente
            while(AwaitingVisit.size() != 0){
                curr = AwaitingVisit.front(); AwaitingVisit.pop_front();
                if(!IsVisited[curr]){
                    IsVisited[curr] = true;
                    for(auto it = Adj[curr].rbegin(); it != Adj[curr].rend(); ++it){
                        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
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();
    ///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());
    ///IsVisited
    IsVisited = vector<bool>(N);
    ///Solutions
    vector<int> SolutionsVtr(Q);

    if(N <= 5000 && Q <= 5000 && C <= 5000){
        ///Adjacency lists
        vector< set<int> > Adj(N);
        ///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;
    }

    bool Group2 = true;
    for(int i = 0; i < C; ++i){
        if(CollapsesDqe[i].Town != CollapsesDqe[i+1].Town){
            Group2 = false;
            break;
        }
    }

    if(Group2){
        const int W = CollapsesDqe.front().Town;
        ///Adjacency lists
        vector< set<int> > Adj(N);
        ///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.Left <= W && W < 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 = solve2(Adj);
                SolutionsVtr[currCollapse.Index] = currSolution;
    //            cout << "SOLUTION: " << currSolution << endl;
                if(CollapsesDqe.size() == 0) break;
            }
        }
        return SolutionsVtr;




    }

    return vector<int>(0);

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 632 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 7 ms 668 KB Output is correct
5 Correct 10 ms 948 KB Output is correct
6 Correct 515 ms 1668 KB Output is correct
7 Correct 192 ms 1668 KB Output is correct
8 Correct 167 ms 1668 KB Output is correct
9 Correct 215 ms 1668 KB Output is correct
10 Correct 279 ms 1668 KB Output is correct
11 Correct 940 ms 1780 KB Output is correct
12 Correct 860 ms 1840 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 3888 KB Output is correct
2 Correct 64 ms 3888 KB Output is correct
3 Incorrect 72 ms 7512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 7512 KB Output is correct
2 Incorrect 92 ms 7512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 632 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 7 ms 668 KB Output is correct
5 Correct 10 ms 948 KB Output is correct
6 Correct 515 ms 1668 KB Output is correct
7 Correct 192 ms 1668 KB Output is correct
8 Correct 167 ms 1668 KB Output is correct
9 Correct 215 ms 1668 KB Output is correct
10 Correct 279 ms 1668 KB Output is correct
11 Correct 940 ms 1780 KB Output is correct
12 Correct 860 ms 1840 KB Output is correct
13 Correct 58 ms 3888 KB Output is correct
14 Correct 64 ms 3888 KB Output is correct
15 Incorrect 72 ms 7512 KB Output isn't correct
16 Halted 0 ms 0 KB -