답안 #70891 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70891	2018-08-23T15:56:44 Z	dmfr	Collapse (JOI18_collapse)	C++11	5 / 100	15000 ms	12088 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);
    }
};

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

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

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

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

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

답안 #70891

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