| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 784590 | Denkata | 다리 (APIO19_bridges) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int crit = 1000;
const int maxn = 1e6+3;
int i,j,p,q,n,m,k,Q,br,d,new_w[maxn],ans[maxn+3];
int used[maxn];
struct Query
{
int type;
int first,second;
int ind;
};
struct Edge
{
int u,v,d;
};
vector <pair<int,int>> changed;
vector <Edge> v;
vector <Query> a,b;
bool fff(Query a,Query b)
{
if(a.second!=b.second) return a.second>b.second;
return a.type>b.type;
}
int par[maxn],sz[maxn];
int Find(int p)
{
if(par[p]==p)
return p;
return Find(par[p]);
}
struct Roll_back
{
int a,sza;
int b,szb;
};
stack <Roll_back> st;
void Union(int p,int q,bool fl)
{
p = Find(p);
q = Find(q);
// cout<<p<<" Union "<<q<<endl;
if(p==q)return ;
if(sz[p]>sz[q])swap(p,q);
if(fl)
st.push({p,sz[p],q,sz[q]});
par[p] = q;
sz[q] += sz[p];
}
void roll_back()
{
while(!st.empty())
{
auto t = st.top();
st.pop();
par[t.a] = t.a;
sz[t.a] = t.sza;
par[t.b] = t.b;
sz[t.b] = t.szb;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
v.push_back({0,0,0});///parser
for(i=1; i<=m; i++)
{
cin>>p>>q>>k;
v.push_back({p,q,k});
}
cin>>Q;
for(i=1; i<=Q; i++)
{
cin>>p>>q>>k;
b.push_back({p,q,k});
}
for(int ii=0; ii<Q; ii+=crit)
{
//cout<<ii<<" query "<<endl;
int R = min(ii+crit-1,Q-1);
for(int jj=ii; jj<=R; jj++)
a.push_back({b[jj].type,b[jj].first,b[jj].second,jj});
++br;
vector <Query> tek;
changed.clear();
tek.clear();
for(auto i:a)
{
if(i.type==1)
{
p = i.first;
q = i.second;
new_w[p] = q;
// cout<<p<<" changed "<<endl;
changed.push_back({p,i.ind});
used[p] = br;
}
else tek.push_back({-1,i.first,i.second,i.ind});
}
for(i=1; i<=m; i++)
{
if(used[i]!=br)
{
// cout<<v[i].u<<" rebra "<<v[i].v<<" "<<v[i].d<<endl;
tek.push_back({v[i].u,v[i].v,v[i].d});
}
}
sort(tek.begin(),tek.end(),fff);
for(i=0; i<=n+1; i++)
par[i] = i,sz[i] = 1;
for(auto i:tek)
{
if(i.type!=-1)
{
p = i.type;
q = i.first;
// cout<<p<<" dobavqne "<<q<<endl;
Union(p,q,0);
}
else
{
for(auto j:changed)
{
// cout<<j.second<<" "<<v[j.first].d<<endl;
if((b[j.second].second>=i.second && j.second<i.ind) || (j.second>i.ind && v[j.first].d>=i.second))
{
Union(v[j.first].u,v[j.first].v,true);
}
}
// cout<<i.ind<<" "<<sz[Find(i.first)]<<endl;
ans[i.ind] = sz[Find(i.first)];
roll_back();
}
}
for(auto i:a)
if(i.type==1)v[i.first] = i.second;
a.clear();
}
for(i=0;i<Q;i++)
{
if(b[i].type==2)
cout<<ans[i]<<endl;
}
return 0;
}
///if an edge is updated more than once during the same bucket query processing!