oj.uz

Submission #70928

# Submission time Handle Problem Language Result Execution time Memory
70928 2018-08-23T17:41:03 Z dmfr Collapse (JOI18_collapse) C++11
5 / 100
 15000 ms 8712 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);


    bool Group2 = true;
    for(int i = 0; i < Q-1; ++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;




    }



    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;
    }


    return vector<int>(0);

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 632 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 7 ms 684 KB Output is correct
4 Correct 8 ms 684 KB Output is correct
5 Correct 9 ms 804 KB Output is correct
6 Correct 486 ms 1508 KB Output is correct
7 Correct 181 ms 1508 KB Output is correct
8 Correct 180 ms 1508 KB Output is correct
9 Correct 175 ms 1508 KB Output is correct
10 Correct 280 ms 1508 KB Output is correct
11 Correct 929 ms 1836 KB Output is correct
12 Correct 937 ms 1924 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 3756 KB Output is correct
2 Correct 73 ms 3756 KB Output is correct
3 Correct 161 ms 7340 KB Output is correct
4 Correct 110 ms 7340 KB Output is correct
5 Correct 367 ms 7364 KB Output is correct
6 Correct 5816 ms 7364 KB Output is correct
7 Execution timed out 15068 ms 8712 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 8712 KB Output is correct
2 Incorrect 28 ms 8712 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 632 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 7 ms 684 KB Output is correct
4 Correct 8 ms 684 KB Output is correct
5 Correct 9 ms 804 KB Output is correct
6 Correct 486 ms 1508 KB Output is correct
7 Correct 181 ms 1508 KB Output is correct
8 Correct 180 ms 1508 KB Output is correct
9 Correct 175 ms 1508 KB Output is correct
10 Correct 280 ms 1508 KB Output is correct
11 Correct 929 ms 1836 KB Output is correct
12 Correct 937 ms 1924 KB Output is correct
13 Correct 68 ms 3756 KB Output is correct
14 Correct 73 ms 3756 KB Output is correct
15 Correct 161 ms 7340 KB Output is correct
16 Correct 110 ms 7340 KB Output is correct
17 Correct 367 ms 7364 KB Output is correct
18 Correct 5816 ms 7364 KB Output is correct
19 Execution timed out 15068 ms 8712 KB Time limit exceeded
20 Halted 0 ms 0 KB -