| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1254642 | minhpk | Collapse (JOI18_collapse) | C++20 | 0 ms | 0 KiB |
#include "collapse.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b,c;
vector<int> t;
vector<int> z;
vector<int> z1;
vector<int> w;
vector<int> w1;
vector <int> res;
map<pair<int,int>,int> m;
struct edge{
int x,y,l,r;
};
vector <edge> vec;
vector<pair<int,int>> f[4000005];
void update(int id,int l,int r,int x,int y,pair<int,int> val){
if (x>r || y<l){
return;
}
if (l>=x && y>=r){
f[id].push_back(val);
return;
}
int mid=(l+r)/2;
update(id*2,l,mid,x,y,val);
update(id*2+1,mid+1,r,x,y,val);
}
vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
a=N;
t=T;
z=X;
z1=Y;
w=W;
w1=P;
b=t.size();
c=w.size();
for (int i=1;i<=b;i++){
int x=z[i-1];
int y=z1[i-1];
int type=t[i-1];
if (type==0){
m[{x,y}]=i;
m[{y,x}]=i;
}else{
vec.push_back({x,y,m[{x,y}],i-1});
m[{x,y}]=0;
m[{y,x}]=0;
}
}
for (auto p:m){
if (p.second!=0){
vec.push_back({p.first.first,p.first.second,p.second,b});
}
}
for (auto p:vec){
auto [x,y,l,r]=p;
pair<int,int> pre={x,y};
update(1,1,b,l,r,pre);
}
return res;
}