| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 203084 | Mercenary | Bridges (APIO19_bridges) | C++14 | 0 ms | 0 KiB |
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>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#define pb push_back
#define mp make_pair
#define taskname "A"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
struct Dsurollback{
pair<int*,int> data[(int)2e6];
int lab[maxn] , sz;
int FindLab(int u){
return lab[u] < 0 ? u : FindLab(lab[u]);
}
void Change(int & u , int v){
data[sz++] = mp(&u,u);
u = v;
}
void rollback(int sz1){
while(sz > sz1){
(*data[sz-1].first) = data[sz-1].second;
--sz;
}
}
int cnt = 0;
int cnt1 = 0;
void Merge(int u , int v){
u = FindLab(u);v = FindLab(v);
if(u == v)return;
if(lab[u] > lab[v])swap(u,v);
Change(lab[u],lab[u]+lab[v]);
Change(lab[v],u);
}
int cur(){return sz;};
void reset(int n){
fill_n(lab,n+2,-1);
sz = 0;
}
}Dsu;
int n , m , q;
int u[maxn] , v[maxn] , d[maxn];
int out[maxn] , fakeid[maxn];
int type[maxn];
int res[maxn];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen(taskname".INP","r")){
freopen(taskname".INP", "r",stdin);
freopen(taskname".OUT", "w",stdout);
}
cin >> n >> m;
for(int i = 1 ; i <= m ; ++i){
cin >> u[i] >> v[i] >> d[i];
fakeid[i] = i;
}
cin >> q;
for(int i = m + 1 ; i <= q + m ; ++i){
cin >> type[i];
if(type[i] == 1){
int x;cin >> x;
u[i] = u[x];v[i] = v[x];cin >> d[i];
out[fakeid[x]] = i;
fakeid[x] = i;
}else{
cin >> u[i] >> d[i];
}
}
for(int i = 1 ; i <= m + q ; ++i)if(out[i] == 0)out[i] = q + m + 1;
const int MAGIC = 300;
vector<int> prepare;
for(int i = 1 ; i <= m + q ; ++i)if(type[i] != 2)prepare.pb(i);
sort(prepare.begin(),prepare.end() , [&](const int x , const int y){return d[x] > d[y];});
for(int l = m + 1 ; l <= m + q ; l += MAGIC){
int r = min(m + q ,l+MAGIC-1);
vector<int> qval;
Dsu.reset(n);
vector<int> sp , norm;
for(int i = l ; i <= r ; ++i){
if(type[i] == 2 && i >= l)qval.pb(i);
}
for(auto & i : prepare){
if(i > r || out[i] < l)continue;
if(i < l && out[i] > r)norm.pb(i);
else sp.pb(i);
}
sort(qval.begin(),qval.end(),[&](const int x , const int y){return d[x] > d[y];});
int it = 0;
for(auto & id : qval){
while(it < norm.size() && d[id] <= d[norm[it]]){
Dsu.Merge(u[norm[it]],v[norm[it]]);
++it;
}
int tmp = Dsu.cur();
for(auto & c : sp){
if(d[id] > d[c])break;
if(d[id] <= d[c] && c < id && out[c] > id){
Dsu.Merge(u[c],v[c]);
}
}
res[id] = -Dsu.lab[Dsu.FindLab(u[id])];
Dsu.rollback(tmp);
}
}
for(int i = m + 1 ; i <= m + q ; ++i)if(type[i] == 2)cout << res[i] << '\n';
}
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#define pb push_back
#define mp make_pair
#define taskname "A"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
struct Dsurollback{
pair<int*,int> data[(int)2e6];
int lab[maxn] , sz;
int FindLab(int u){
return lab[u] < 0 ? u : FindLab(lab[u]);
}
void Change(int & u , int v){
data[sz++] = mp(&u,u);
u = v;
}
void rollback(int sz1){
while(sz > sz1){
(*data[sz-1].first) = data[sz-1].second;
--sz;
}
}
int cnt = 0;
int cnt1 = 0;
void Merge(int u , int v){
u = FindLab(u);v = FindLab(v);
if(u == v)return;
if(lab[u] > lab[v])swap(u,v);
Change(lab[u],lab[u]+lab[v]);
Change(lab[v],u);
}
int cur(){return sz;};
void reset(int n){
fill_n(lab,n+2,-1);
sz = 0;
}
}Dsu;
int n , m , q;
int u[maxn] , v[maxn] , d[maxn];
int out[maxn] , fakeid[maxn];
int type[maxn];
int res[maxn];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen(taskname".INP","r")){
freopen(taskname".INP", "r",stdin);
freopen(taskname".OUT", "w",stdout);
}
cin >> n >> m;
for(int i = 1 ; i <= m ; ++i){
cin >> u[i] >> v[i] >> d[i];
fakeid[i] = i;
}
cin >> q;
for(int i = m + 1 ; i <= q + m ; ++i){
cin >> type[i];
if(type[i] == 1){
int x;cin >> x;
u[i] = u[x];v[i] = v[x];cin >> d[i];
out[fakeid[x]] = i;
fakeid[x] = i;
}else{
cin >> u[i] >> d[i];
}
}
for(int i = 1 ; i <= m + q ; ++i)if(out[i] == 0)out[i] = q + m + 1;
const int MAGIC = 300;
vector<int> prepare;
for(int i = 1 ; i <= m + q ; ++i)if(type[i] != 2)prepare.pb(i);
sort(prepare.begin(),prepare.end() , [&](const int x , const int y){return d[x] > d[y];});
for(int l = m + 1 ; l <= m + q ; l += MAGIC){
int r = min(m + q ,l+MAGIC-1);
vector<int> qval;
Dsu.reset(n);
vector<int> sp , norm;
for(int i = l ; i <= r ; ++i){
if(type[i] == 2 && i >= l)qval.pb(i);
}
for(auto & i : prepare){
if(i > r || out[i] < l)continue;
if(i < l && out[i] > r)norm.pb(i);
else sp.pb(i);
}
sort(qval.begin(),qval.end(),[&](const int x , const int y){return d[x] > d[y];});
int it = 0;
for(auto & id : qval){
while(it < norm.size() && d[id] <= d[norm[it]]){
Dsu.Merge(u[norm[it]],v[norm[it]]);
++it;
}
int tmp = Dsu.cur();
for(auto & c : sp){
if(d[id] > d[c])break;
if(d[id] <= d[c] && c < id && out[c] > id){
Dsu.Merge(u[c],v[c]);
}
}
res[id] = -Dsu.lab[Dsu.FindLab(u[id])];
Dsu.rollback(tmp);
}
}
for(int i = m + 1 ; i <= m + q ; ++i)if(type[i] == 2)cout << res[i] << '\n';
}