| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 319735 | Everule | 자매 도시 (APIO20_swap) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
struct Persistent_DSU{
int n;
vector<int> par;
vector<int> partime;
struct state{
int edges, size, time;
state(int edges, int size,int time) : edges(edges), size(size), time(time) {}
state() {}
bool operator<(const state &o){
return time<o.time;
}
bool operator<(int t){
return time < t;
}
};
vector<vector<state>> sz;
int currtime = 0;
Persistent_DSU(int n) : n(n){
par.resize(n);
iota(par.begin(), par.end(), 0);
partime.assign(n, -1);
sz.assign(n, {state(0,1,0)});
}
int find_set(int u,int t){
while(par[u] != u && partime[u] < t){
u = par[u];
}
return u;
}
void join_sets(int u,int v){
int r1 = find_set(u, currtime);
int r2 = find_set(v, currtime);
if(r1 == r2){
auto s = sz[r1].back();
s.edges++;
s.time = currtime;
sz[r1].push_back(s);
++currtime;
return;
}
auto [e1,s1,t1] = sz[r1].back();
auto [e2,s2,t2] = sz[r2].back();
if(s1 > s2){
swap(r1,r2);
}
par[r1] = r2;
partime[r1] = currtime;
sz[r2].push_back(state(e1+e2+1,s1+s2,currtime));
++currtime;
}
state findstate(int u,int t){
auto it = lower_bound(sz[u].begin(), sz[u].end(), t);
--it;
return (*it);
}
};
const int INF = 1e9;
struct Edge{
int u,v,w;
Edge(int u,int v,int w) : u(u), v(v), w(w) {}
Edge() {}
bool operator<(const Edge &o){
return w < o.w;
}
};
Persistent_DSU dsu;
vector<Edge> edges;
int init(int n,int m, int u[], int v[], int w[]){
edges.resize(m);
for(int i=0;i<m;i++){
edges[i] = Edge(u[i],v[i],w[i]);
}
Persistent_DSU dsu(n);
sort(edges.begin(), edges.end());
for(const auto &[u,v,w] : edges){
dsu.join_sets(u,v);
}
}
int getminimumFuelCapacity(int x,int y){
int mn = 1, mx = edges.size() + 1;
while(mn < mx){
int mid = mn + mx;
mid>>=1;
int r1 = dsu.find_set(x, mid);
int r2 = dsu.find_set(y, mid);
if(r1 != r2){
mn = mid + 1;
continue;
}
auto s = dsu.findstate(r1, mid);
if(s.edges < s.size){
mn = mid + 1;
}
else{
mx = mid;
}
}
if(mn == edges.size() + 1) return -1;
else return edges[mn-1].w;
}