# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
208995 | jtnydv25 | 다리 (APIO19_bridges) | C++14 | 3093 ms | 9576 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sd(x) scanf("%d", &(x))
#define pii pair<int, int>
#define F first
#define S second
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#define ld long double
template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
os<<"("<<p.first<<", "<<p.second<<")";
return os;
}
template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
os<<"{";
for(int i = 0;i < (int)v.size(); i++){
if(i)os<<", ";
os<<v[i];
}
os<<"}";
return os;
}
#ifdef LOCAL
#define cerr cout
#else
#endif
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
template<class T>
struct rollback_array{
struct ct{
int where;
T what;
};
stack<ct> changes;
vector<T> arr;
int n;
rollback_array(){n = 0;}
rollback_array(int n) : n(n), arr(n){};
void setall(T x){
for(int i = 0; i < n; i++) arr[i] = x;
}
// if not to be rolled back just do arr[x] = v
int & operator [] (int x){ return arr[x];}
void update(int i, T v){
changes.push({i, arr[i]});
arr[i] = v;
}
void click(){
changes.push({-1, T()});
}
void roll_back(){
while(!changes.empty()){
auto it = changes.top();
changes.pop();
if(it.where == -1) return;
arr[it.where] = it.what;
}
}
};
struct rollback_dsu{
int n;
rollback_array<int> par, num;
rollback_dsu(int n) : n(n), par(n), num(n){
par.setall(-1);
num.setall(1);
}
int root(int x){
if(par[x] == -1) return x;
int rt = root(par[x]);
par.update(x, rt);
return rt;
}
void merge(int x, int y){
x = root(x);
y = root(y);
if(x == y) return;
par.update(x, y);
int _num = num[x] + num[y];
num.update(y, _num);
}
void click(){
par.click();
num.click();
}
void roll_back(){
par.roll_back();
num.roll_back();
}
};
const int N = 100005;
int a[N], b[N], w[2 * N];
int type[N], s[N];
bool changing[N];
const int BLOCK = 505;
int ans[N];
int main(){
int n = 50000, m = 100000;
sd(n); sd(m);
rollback_array<int> W(m);
for(int i = 0; i < m; i++){
a[i] = rand() % n + 1; b[i] = rand() % n + 1; w[i] = rand() % 1000000;
sd(a[i]); sd(b[i]); sd(w[i]);
a[i]--; b[i]--;
W[i] = w[i];
}
int q = 100000;
sd(q);
for(int i = 0; i < q; i++){
type[i] = rand() % 2 + 1;
if(type[i]==1) s[i] = rand() % m + 1;
else s[i] = rand() % n + 1;
w[i + m] = rand() % 1000000;
// sd(type[i]); sd(s[i]); sd(w[i + m]);
s[i]--;
}
for(int i = 0; i * BLOCK < q; i++){
rollback_dsu D(n);
vector<int> perm(m);
iota(all(perm), 0);
int st = i * BLOCK, en = min(q - 1, st + BLOCK - 1);
memset(changing, 0, sizeof changing);
vector<int> updates;
for(int j = st; j <= en; j++){
if(type[j] == 1){
changing[s[j]] = 1;
} else{
perm.push_back(j + m);
}
}
sort(all(perm), [&](int i, int j){return (w[i] > w[j]) || (w[i] == w[j] && i < j);});
vector<int> changing_edges;
for(int j = 0; j < m; j++) if(changing[j]) changing_edges.push_back(j);
if(sz(perm) > m){
for(int j = 0; j < sz(perm); j++){
int ind = perm[j];
if(ind < m){
if(!changing[ind]){
D.merge(a[ind], b[ind]);
}
} else{
ind -= m;
D.click();
W.click();
for(int j = st; j < ind; j++){
if(type[j] == 1) W.update(s[j], w[j + m]);
}
for(int e : changing_edges) if(W[e] >= w[ind + m]){
D.merge(a[e], b[e]);
}
ans[ind] = D.num[D.root(s[ind])];
D.roll_back();
W.roll_back();
}
}
}
for(int j = st; j <= en; j++) if(type[j] == 1){
w[s[j]] = w[j + m];
// W[s[j]] = w[j + m];
}
}
for(int i = 0; i < q; i++) if(type[i] == 2) printf("%d\n", ans[i]);
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |