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<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define tiii tuple<int, int, int>
#define toi_is_so_de ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef local
void CHECK();
void setio(){
freopen("/Users/iantsai/cpp/input.txt","r",stdin);
freopen("/Users/iantsai/cpp/output.txt","w",stdout);
}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
const int mxn = 5e4+5, mxm = 1e5+5, siz = sqrt(mxm);
int n, m, q, v[mxm], id[mxm], ans[mxm], changed[mxm];
tiii edges[mxm];
bool vis[mxm];
struct DSU {
int to[mxn], num[mxn];
vector<int> temp;
void init(int n){
for(int i = 1; i <= n; i++){
to[i] = i;
num[i] = 1;
}
}
int find(int x){
return x == to[x] ? x : to[x] = find(to[x]);
}
bool merge(int x, int y){
debug(x, y);
x = find(x), y = find(y);
if(x == y)return false;
if(num[x] < num[y])swap(x, y);
temp.pb(y);
to[y] = x;
num[x] += num[y];
return true;
}
void undo(int ed){
debug(sz(temp), ed);
while(sz(temp) > ed){
auto y = temp.back();
num[to[y]] -= num[y];
to[y] = y;
temp.pop_back();
}
}
}d;
signed main(){
setio();
toi_is_so_de;
cin >> n >> m;
for(int i=1;i<=m;i++){
int a, b, c;
cin >> a >> b >> c;
edges[i] = {a, b, c};
}
int ord[m+1];
for(int i=1;i<=m;i++){
ord[i] = i;
}
sort(ord+1, ord+1+m, [&](int a, int b){return get<2>(edges[a]) > get<2>(edges[b]);});
cin >> q;
for(int i=1;i<=q;i+=siz){
d.init(n);
vector<tiii>qres;
vector<int>temp;
for(int j=i;j<=min(q, i+siz-1);j++){
int ty, x, y;
cin >> ty >> x >> y;
if(ty == 1){
changed[x] = j;
id[j] = x, v[j] = y;
temp.pb(x);
}
else{
qres.pb({y, x, j});
}
}
sort(all(temp));
temp.resize(unique(all(temp))-temp.begin());
int pos = 0;
sort(all(qres), greater<tiii>());
for(auto [w, st, t] : qres){
while(pos+1 <= m and get<2>(edges[ord[pos+1]])>=w){
pos++;
if(changed[ord[pos]] == 0) d.merge(get<0>(edges[ord[pos]]), get<1>(edges[ord[pos]]));
}
int ro = sz(d.temp);
for(int j=t;j>=i;j--){
if(!id[j] or vis[id[j]])continue;
vis[id[j]] = 1;
if(v[j]>=w){
d.merge(get<0>(edges[id[j]]),get<1>(edges[id[j]]));
}
}
for(auto x:temp){
if(vis[x]) vis[x] = 0;
else if(get<2>(edges[x])>=w){
d.merge(get<0>(edges[x]),get<1>(edges[x]));
debug("1");
}
}
ans[t] = d.num[d.find(st)];
d.undo(ro);
}
for(int j=i;j<=min(q,i+siz-1);j++){
if(id[j]){
changed[id[j]] = 0;
get<2>(edges[id[j]]) = v[j];
}
}
}
for(int i=1;i<=q;i++){
if(ans[i])cout<< ans[i] << '\n';
}
}
#ifdef local
void CHECK(){
cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
function<bool(string,string)> compareFiles = [](string p1, string p2)->bool {
std::ifstream file1(p1);
std::ifstream file2(p2);
if (!file1.is_open() || !file2.is_open())return false;
std::string line1, line2;
while (getline(file1, line1) && getline(file2, line2)) {
if (line1 != line2)return false;
}
int cnta=0,cntb=0;
while(getline(file1,line1))cnta++;
while(getline(file2,line2))cntb++;
return cntb-cnta<=1;
};
bool check = compareFiles("output.txt","expected.txt");
if (check) cerr<<"ACCEPTED\n";
else cerr<<"WRONG ANSWER!\n";
}
#else
#endif
# | 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... |