답안 #70906 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70906	2018-08-23T16:25:12 Z	dmfr	Collapse (JOI18_collapse)	C++11	5 / 100	15000 ms	10780 KB

collapse

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #70906

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