이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#ifdef _DEBUG
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)
#define ins insert
#define ssize(x) (int((x).size()))
#define bs(args...) binary_search(args)
#define lb(args...) lower_bound(args)
#define ub(args...) upper_bound(args)
#define all(x) (x).begin(),(x).end()
#define mp(a, b) make_pair(a, b)
#define mt(args...) make_tuple(args)
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define die exit(0)
template<typename T>
using vc = vector<T>;
template<typename T>
using uset = unordered_set<T>;
template<typename A, typename B>
using umap = unordered_map<A, B>;
template<typename T, typename Comp>
using pq = std::priority_queue<T, vc<T>, Comp>;
template<typename T>
using maxpq = pq<T, less<T>>;
template<typename T>
using minpq = pq<T, greater<T>>;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using db = double;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vc<int>;
using vll = vc<ll>;
using vpi = vc<pi>;
using vpll = vc<pll>;
using str = string;
constexpr char el = '\n';
constexpr char sp = ' ';
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3fLL;
// ---------------------------------------------------------------------
const int M = 1e5+5;
const int Q = M;
int n, m, q, bsz, t[Q], x[Q], y[Q], ans[Q];
struct edge {
int v, u, w;
} e[M];
struct dsu {
vi lk, sz, un;
dsu(int n){
lk.resize(n);
sz.resize(n);
iota(all(lk), 0);
fill(all(sz), 1);
}
int root(int a){
while(a^lk[a])
a = lk[a];
return a;
}
void join(int a, int b){
a = root(a);
b = root(b);
if(a==b)
return;
if(sz[a]<sz[b])
swap(a, b);
un.pb(b);
lk[b] = a;
sz[a] += sz[b];
}
void undo(){
int b = un.back();
sz[lk[b]] -= sz[b];
lk[b] = b;
un.pop_back();
}
void undo(int x){
while(ssize(un)>x)
undo();
}
};
struct bset {
bitset<M> b;
vi op;
void set(int i){
if(b[i])
return;
op.pb(i);
b[i] = 1;
}
bool at(int i){
return b[i];
}
void clear(){
while(!op.empty()){
b[op.back()] = 0;
op.pop_back();
}
}
} bset;
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cout << fixed; clog << fixed; clog << unitbuf;
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("debug.txt", "w", stderr);
#else
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
#endif
cin >> n >> m;
for(int i = 1; i <= m; ++i)
cin >> e[i].v >> e[i].u >> e[i].w;
cin >> q;
bsz = sqrt(q);
for(int i = 0; i < q; ++i) {
cin >> t[i] >> x[i] >> y[i];
// if t[i] == 1, then:
// bridge x[i] now has weight y[i]
// else
// car with weight y[i] is on node x[i]
}
for(int l = 0; l < q; l += bsz){
int r = min(l + bsz, q);
vc<bool> changed(m+1);
vi ask, upd;
for(int i = l; i < r; ++i) {
if (t[i] == 1) {
changed[x[i]] = 1;
upd.pb(i);
}else
ask.pb(i);
}
sort(all(ask), [](int i, int j){
return y[i] > y[j];
});
vc<edge> unchanged;
for(int i = 1; i <= m; ++i)
if(!changed[i])
unchanged.pb(e[i]);
sort(all(unchanged), [](edge a, edge b){
return a.w < b.w;
});
dsu d(n+1);
int p = -1;
for(int i: ask){
while(!unchanged.empty()&&unchanged.back().w>=y[i]) {
d.join(unchanged.back().v, unchanged.back().u);
unchanged.pop_back();
}
while(p+1<ssize(upd)&&upd[p+1]<i)
++p;
int prev_size = ssize(d.un);
bset.clear();
for(int k = p; k >= 0; --k) {
int j = upd[k];
if (!bset.at(x[j])) {
bset.set(x[j]);
if (y[j] >= y[i])
d.join(e[x[j]].v, e[x[j]].u);
}
}
for(int k = p+1; k < ssize(upd); ++k) {
int j = upd[k];
if (!bset.at(x[j]) && e[x[j]].w >= y[i])
d.join(e[x[j]].v, e[x[j]].u);
}
ans[i] = d.sz[d.root(x[i])];
d.undo(prev_size);
}
for(int i = l; i < r; ++i)
if(t[i]==1)
e[x[i]].w = y[i];
}
for(int i = 0; i < q; ++i)
if(t[i]==2)
cout << ans[i] << el;
}
# | 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... |