| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 145968 | Bodo171 | 다리 (APIO19_bridges) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
const int nmax=100005;
const int buck=300;
struct event
{
int tip,id;
}ev;
vector<event> evs[2*nmax];
vector<int> spec;
vector<int> norm;
map<int,int> act;
int tt[nmax],rg[nmax],mic[nmax],mare[nmax],a[nmax],b[nmax],w[nmax],tip[nmax],wh[nmax],cost[nmax],ap[nmax],ans[nmax],ini[nmax];
int ops,n,m,q,i,nr,j;
int finds(int x)
{
while(x!=tt[x])
x=tt[x];
return x;
}
void unite(int A,int B)
{
if(A==B) return;
if(rg[A]<rg[B]) swap(A,B);
++ops;
mic[ops]=B;mare[ops]=A;
tt[B]=A;rg[A]+=rg[B];
}
void rollback(int lim)
{
while(ops>lim)
{
tt[mic[ops]]=mic[ops];
rg[mare[ops]]-=rg[mic[ops]];
ops--;
}
}
int main()
{
//freopen("data.in","r",stdin);
ios_base::sync_with_stdio(false);
cin>>n>>m;
for(i=1;i<=m;i++)
{
cin>>a[i]>>b[i]>>w[i];
norm.push_back(w[i]);
}
cin>>q;
for(i=1;i<=q;i++)
{
cin>>tip[i]>>wh[i]>>cost[i];
norm.push_back(cost[i]);
}
sort(norm.begin(),norm.end());
norm.erase(unique(norm.begin(),norm.end()),norm.end());
int lim=norm.size();
for(i=0;i<norm.size();i++)
act[norm[i]]=i+1;
for(i=1;i<=m;i++)
w[i]=act[w[i]];
for(i=1;i<=q;i++)
cost[i]=act[cost[i]];
for(int bg=1;bg<=q;bg+=buck)
{
nr=0;
ops=0;
spec.clear();
for(i=1;i<=n;i++)
tt[i]=i,rg[i]=1;
for(i=bg;i<min(bg+buck,q+1);i++)
{
if(tip[i]==1)
{
spec.push_back(wh[i]);
ap[wh[i]]=1;
ini[wh[i]]=w[wh[i]];
}
else
{
evs[cost[i]].emplace_back({1,i});
}
}
for(i=1;i<=m;i++)
if(!ap[i])
evs[w[i]].emplace_back({0,i});
int sz;
for(i=lim;i>=1;i--)
{
sz=evs[i].size();
for(int it=sz-1;it>=0;it--)
{
ev=evs[i][it];
if(ev.tip==0)
unite(finds(a[ev.id]),finds(b[ev.id]));
else
{
int ind=ev.id,de_unde=ops;
for(j=bg; j<ind; j++)
if(tip[j]==1)
{
w[wh[j]]=cost[j];
}
for(j=0; j<spec.size(); j++)
if(w[spec[j]]>=i)
{
unite(finds(a[spec[j]]),finds(b[spec[j]]));
}
ans[ind]=rg[finds(wh[ind])];
rollback(de_unde);
for(j=bg; j<ind; j++)
if(tip[j]==1)
{
w[wh[j]]=ini[wh[j]];
}
}
}
}
for(i=1;i<=lim;i++)
evs[i].resize(0);
for(i=bg;i<min(bg+buck,q+1);i++)
if(tip[i]==1)
w[wh[i]]=cost[i];
for(i=0;i<spec.size();i++)
ap[spec[i]]=0;
}
for(i=1;i<=q;i++)
if(tip[i]==2)
cout<<ans[i]<<'\n';
return 0;
}