| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 70908 | dmfr | Collapse (JOI18_collapse) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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
*/
if(N*Q < 5000*5000*10){
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;
}
return vector<int>(0);
}