oj.uz

Submission #70902

# Submission time Handle Problem Language Result Execution time Memory
70902 2018-08-23T16:20:42 Z dmfr Collapse (JOI18_collapse) C++11
5 / 100
 15000 ms 13836 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();
    ///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 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 6 ms 632 KB Output is correct
5 Correct 11 ms 848 KB Output is correct
6 Correct 520 ms 1412 KB Output is correct
7 Correct 202 ms 1412 KB Output is correct
8 Correct 175 ms 1412 KB Output is correct
9 Correct 229 ms 1468 KB Output is correct
10 Correct 295 ms 1608 KB Output is correct
11 Correct 999 ms 1992 KB Output is correct
12 Correct 930 ms 2044 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 4592 KB Output is correct
2 Correct 89 ms 4968 KB Output is correct
3 Correct 194 ms 9148 KB Output is correct
4 Correct 93 ms 9148 KB Output is correct
5 Correct 436 ms 9296 KB Output is correct
6 Correct 6234 ms 9296 KB Output is correct
7 Execution timed out 15017 ms 13408 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 13408 KB Output is correct
2 Correct 87 ms 13408 KB Output is correct
3 Correct 93 ms 13408 KB Output is correct
4 Correct 114 ms 13408 KB Output is correct
5 Correct 760 ms 13408 KB Output is correct
6 Correct 10312 ms 13408 KB Output is correct
7 Execution timed out 15072 ms 13836 KB Time limit exceeded
8 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 6 ms 632 KB Output is correct
5 Correct 11 ms 848 KB Output is correct
6 Correct 520 ms 1412 KB Output is correct
7 Correct 202 ms 1412 KB Output is correct
8 Correct 175 ms 1412 KB Output is correct
9 Correct 229 ms 1468 KB Output is correct
10 Correct 295 ms 1608 KB Output is correct
11 Correct 999 ms 1992 KB Output is correct
12 Correct 930 ms 2044 KB Output is correct
13 Correct 73 ms 4592 KB Output is correct
14 Correct 89 ms 4968 KB Output is correct
15 Correct 194 ms 9148 KB Output is correct
16 Correct 93 ms 9148 KB Output is correct
17 Correct 436 ms 9296 KB Output is correct
18 Correct 6234 ms 9296 KB Output is correct
19 Execution timed out 15017 ms 13408 KB Time limit exceeded
20 Halted 0 ms 0 KB -