oj.uz

Submission #70891

# Submission time Handle Problem Language Result Execution time Memory
70891 2018-08-23T15:56:44 Z dmfr Collapse (JOI18_collapse) C++11
5 / 100
 15000 ms 12088 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);
        }
    }

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

//    cout << "CollapsesDqe: index day town" << endl;
//    for(const auto& it: CollapsesDqe)
//        cout << it.Index << " " << it.Day << " " << it.Town << endl;

    ///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 10 ms 764 KB Output is correct
2 Correct 8 ms 764 KB Output is correct
3 Correct 13 ms 764 KB Output is correct
4 Correct 21 ms 764 KB Output is correct
5 Correct 19 ms 980 KB Output is correct
6 Correct 3823 ms 2228 KB Output is correct
7 Correct 574 ms 2228 KB Output is correct
8 Correct 609 ms 2228 KB Output is correct
9 Correct 650 ms 2228 KB Output is correct
10 Correct 1282 ms 2280 KB Output is correct
11 Correct 4581 ms 3328 KB Output is correct
12 Correct 4673 ms 3356 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 4448 KB Output is correct
2 Correct 115 ms 4836 KB Output is correct
3 Correct 556 ms 9708 KB Output is correct
4 Correct 430 ms 9708 KB Output is correct
5 Correct 2914 ms 11920 KB Output is correct
6 Execution timed out 15062 ms 11920 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 11920 KB Output is correct
2 Correct 147 ms 11920 KB Output is correct
3 Correct 228 ms 11920 KB Output is correct
4 Correct 383 ms 11920 KB Output is correct
5 Correct 4950 ms 11920 KB Output is correct
6 Execution timed out 15010 ms 12088 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 764 KB Output is correct
2 Correct 8 ms 764 KB Output is correct
3 Correct 13 ms 764 KB Output is correct
4 Correct 21 ms 764 KB Output is correct
5 Correct 19 ms 980 KB Output is correct
6 Correct 3823 ms 2228 KB Output is correct
7 Correct 574 ms 2228 KB Output is correct
8 Correct 609 ms 2228 KB Output is correct
9 Correct 650 ms 2228 KB Output is correct
10 Correct 1282 ms 2280 KB Output is correct
11 Correct 4581 ms 3328 KB Output is correct
12 Correct 4673 ms 3356 KB Output is correct
13 Correct 100 ms 4448 KB Output is correct
14 Correct 115 ms 4836 KB Output is correct
15 Correct 556 ms 9708 KB Output is correct
16 Correct 430 ms 9708 KB Output is correct
17 Correct 2914 ms 11920 KB Output is correct
18 Execution timed out 15062 ms 11920 KB Time limit exceeded
19 Halted 0 ms 0 KB -