oj.uz

Submission #70901

# Submission time Handle Problem Language Result Execution time Memory
70901 2018-08-23T16:14:58 Z dmfr Collapse (JOI18_collapse) C++11
5 / 100
 15000 ms 12916 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);
    }
};

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

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


}

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
*/

    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());

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 632 KB Output is correct
2 Correct 8 ms 696 KB Output is correct
3 Correct 11 ms 712 KB Output is correct
4 Correct 17 ms 712 KB Output is correct
5 Correct 17 ms 872 KB Output is correct
6 Correct 3534 ms 2144 KB Output is correct
7 Correct 462 ms 2144 KB Output is correct
8 Correct 471 ms 2144 KB Output is correct
9 Correct 538 ms 2144 KB Output is correct
10 Correct 956 ms 2224 KB Output is correct
11 Correct 4461 ms 3276 KB Output is correct
12 Correct 4116 ms 3392 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 4984 KB Output is correct
2 Correct 110 ms 5372 KB Output is correct
3 Correct 397 ms 10148 KB Output is correct
4 Correct 392 ms 10148 KB Output is correct
5 Correct 2669 ms 12328 KB Output is correct
6 Execution timed out 15020 ms 12328 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 12328 KB Output is correct
2 Correct 125 ms 12328 KB Output is correct
3 Correct 231 ms 12328 KB Output is correct
4 Correct 327 ms 12328 KB Output is correct
5 Correct 4616 ms 12328 KB Output is correct
6 Execution timed out 15014 ms 12916 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 632 KB Output is correct
2 Correct 8 ms 696 KB Output is correct
3 Correct 11 ms 712 KB Output is correct
4 Correct 17 ms 712 KB Output is correct
5 Correct 17 ms 872 KB Output is correct
6 Correct 3534 ms 2144 KB Output is correct
7 Correct 462 ms 2144 KB Output is correct
8 Correct 471 ms 2144 KB Output is correct
9 Correct 538 ms 2144 KB Output is correct
10 Correct 956 ms 2224 KB Output is correct
11 Correct 4461 ms 3276 KB Output is correct
12 Correct 4116 ms 3392 KB Output is correct
13 Correct 92 ms 4984 KB Output is correct
14 Correct 110 ms 5372 KB Output is correct
15 Correct 397 ms 10148 KB Output is correct
16 Correct 392 ms 10148 KB Output is correct
17 Correct 2669 ms 12328 KB Output is correct
18 Execution timed out 15020 ms 12328 KB Time limit exceeded
19 Halted 0 ms 0 KB -