oj.uz

Submission #70906

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

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;


}

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

    IsVisited = vector<bool>(N);

    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 9 ms 632 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 8 ms 632 KB Output is correct
4 Correct 7 ms 632 KB Output is correct
5 Correct 11 ms 756 KB Output is correct
6 Correct 510 ms 1392 KB Output is correct
7 Correct 207 ms 1392 KB Output is correct
8 Correct 185 ms 1392 KB Output is correct
9 Correct 162 ms 1392 KB Output is correct
10 Correct 277 ms 1392 KB Output is correct
11 Correct 944 ms 1696 KB Output is correct
12 Correct 911 ms 1832 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 3728 KB Output is correct
2 Correct 81 ms 3752 KB Output is correct
3 Correct 160 ms 7336 KB Output is correct
4 Correct 97 ms 7336 KB Output is correct
5 Correct 407 ms 7336 KB Output is correct
6 Correct 6391 ms 7336 KB Output is correct
7 Execution timed out 15083 ms 10780 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 10780 KB Output is correct
2 Correct 66 ms 10780 KB Output is correct
3 Correct 114 ms 10780 KB Output is correct
4 Correct 128 ms 10780 KB Output is correct
5 Correct 869 ms 10780 KB Output is correct
6 Correct 10089 ms 10780 KB Output is correct
7 Execution timed out 15041 ms 10780 KB Time limit exceeded
8 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 8 ms 632 KB Output is correct
4 Correct 7 ms 632 KB Output is correct
5 Correct 11 ms 756 KB Output is correct
6 Correct 510 ms 1392 KB Output is correct
7 Correct 207 ms 1392 KB Output is correct
8 Correct 185 ms 1392 KB Output is correct
9 Correct 162 ms 1392 KB Output is correct
10 Correct 277 ms 1392 KB Output is correct
11 Correct 944 ms 1696 KB Output is correct
12 Correct 911 ms 1832 KB Output is correct
13 Correct 55 ms 3728 KB Output is correct
14 Correct 81 ms 3752 KB Output is correct
15 Correct 160 ms 7336 KB Output is correct
16 Correct 97 ms 7336 KB Output is correct
17 Correct 407 ms 7336 KB Output is correct
18 Correct 6391 ms 7336 KB Output is correct
19 Execution timed out 15083 ms 10780 KB Time limit exceeded
20 Halted 0 ms 0 KB -