답안 #70901 :: oj.uz

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

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

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	632 KB	Output is correct
2	Correct	8 ms	696 KB	Output is correct
3	Correct	11 ms	712 KB	Output is correct
4	Correct	17 ms	712 KB	Output is correct
5	Correct	17 ms	872 KB	Output is correct
6	Correct	3534 ms	2144 KB	Output is correct
7	Correct	462 ms	2144 KB	Output is correct
8	Correct	471 ms	2144 KB	Output is correct
9	Correct	538 ms	2144 KB	Output is correct
10	Correct	956 ms	2224 KB	Output is correct
11	Correct	4461 ms	3276 KB	Output is correct
12	Correct	4116 ms	3392 KB	Output is correct

Subtask #2
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	92 ms	4984 KB	Output is correct
2	Correct	110 ms	5372 KB	Output is correct
3	Correct	397 ms	10148 KB	Output is correct
4	Correct	392 ms	10148 KB	Output is correct
5	Correct	2669 ms	12328 KB	Output is correct
6	Execution timed out	15020 ms	12328 KB	Time limit exceeded
7	Halted	0 ms	0 KB	-

Subtask #3
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	85 ms	12328 KB	Output is correct
2	Correct	125 ms	12328 KB	Output is correct
3	Correct	231 ms	12328 KB	Output is correct
4	Correct	327 ms	12328 KB	Output is correct
5	Correct	4616 ms	12328 KB	Output is correct
6	Execution timed out	15014 ms	12916 KB	Time limit exceeded
7	Halted	0 ms	0 KB	-

Subtask #4
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	632 KB	Output is correct
2	Correct	8 ms	696 KB	Output is correct
3	Correct	11 ms	712 KB	Output is correct
4	Correct	17 ms	712 KB	Output is correct
5	Correct	17 ms	872 KB	Output is correct
6	Correct	3534 ms	2144 KB	Output is correct
7	Correct	462 ms	2144 KB	Output is correct
8	Correct	471 ms	2144 KB	Output is correct
9	Correct	538 ms	2144 KB	Output is correct
10	Correct	956 ms	2224 KB	Output is correct
11	Correct	4461 ms	3276 KB	Output is correct
12	Correct	4116 ms	3392 KB	Output is correct
13	Correct	92 ms	4984 KB	Output is correct
14	Correct	110 ms	5372 KB	Output is correct
15	Correct	397 ms	10148 KB	Output is correct
16	Correct	392 ms	10148 KB	Output is correct
17	Correct	2669 ms	12328 KB	Output is correct
18	Execution timed out	15020 ms	12328 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-

답안 #70901

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