답안 #70926 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70926	2018-08-23T17:36:50 Z	dmfr	Collapse (JOI18_collapse)	C++11	5 / 100	940 ms	7512 KB

collapse

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

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

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




    }

    return vector<int>(0);

}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	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	7 ms	668 KB	Output is correct
5	Correct	10 ms	948 KB	Output is correct
6	Correct	515 ms	1668 KB	Output is correct
7	Correct	192 ms	1668 KB	Output is correct
8	Correct	167 ms	1668 KB	Output is correct
9	Correct	215 ms	1668 KB	Output is correct
10	Correct	279 ms	1668 KB	Output is correct
11	Correct	940 ms	1780 KB	Output is correct
12	Correct	860 ms	1840 KB	Output is correct

Subtask #2
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	58 ms	3888 KB	Output is correct
2	Correct	64 ms	3888 KB	Output is correct
3	Incorrect	72 ms	7512 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	59 ms	7512 KB	Output is correct
2	Incorrect	92 ms	7512 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 35.0

#	결과	실행 시간	메모리	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	7 ms	668 KB	Output is correct
5	Correct	10 ms	948 KB	Output is correct
6	Correct	515 ms	1668 KB	Output is correct
7	Correct	192 ms	1668 KB	Output is correct
8	Correct	167 ms	1668 KB	Output is correct
9	Correct	215 ms	1668 KB	Output is correct
10	Correct	279 ms	1668 KB	Output is correct
11	Correct	940 ms	1780 KB	Output is correct
12	Correct	860 ms	1840 KB	Output is correct
13	Correct	58 ms	3888 KB	Output is correct
14	Correct	64 ms	3888 KB	Output is correct
15	Incorrect	72 ms	7512 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

답안 #70926

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 30.0

Subtask #3 0 / 30.0

Subtask #4 0 / 35.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 30.0

Subtask #3
0 / 30.0

Subtask #4
0 / 35.0