Submission #302229

#TimeUsernameProblemLanguageResultExecution timeMemory
302229vipghn2003Bridges (APIO19_bridges)C++14
13 / 100
3098 ms6092 KiB
#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
using namespace std;

const int N=5e4+5;
const int M=1e5+5;
int n,m,q,u[M],v[M],w[M],res[M],p[N],sz[N],cur,tmpw[M];
bool change[M],vis[N];
vector<int>edge,adj[N],go;
vector<tuple<int,int,int>>query[3];

template<typename T> inline void Cin(T &x)
{
    char c=getchar();
    x=0;
    while (c < '0' || c >'9')
        c = getchar();
    while (c>='0'&&c<='9')
        x=x*10+c-'0',c = getchar();
}
template <typename T, typename... Args> inline void Cin(T& a, Args&... args)
{
    Cin(a);
    Cin(args...);
}

int Find(int x)
{
    if(x==p[x]) return x;
    return x=Find(p[x]);
}

void link(int u,int v)
{
    u=Find(u);
    v=Find(v);
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void Union(int u,int v)
{
    u=Find(u);
    v=Find(v);
    if(u==v) return ;
    p[u]=v;
    sz[v]+=sz[u];
}

void dfs(int u)
{
    vis[u]=true;
    go.push_back(u);
    for(auto&v:adj[u]) if(!vis[v]) dfs(v);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    Cin(n,m);
    for(int i=1;i<=m;i++) Cin(u[i],v[i],w[i]);
    Cin(q);
    int SQ=sqrt(q);
    for(int i=1;i<=q;i++)
    {
        int type,k,d;
        Cin(type,k,d);
        if(type==1) change[k]=true;
        query[type].push_back(make_tuple(d,k,i));
        if(i%SQ==0||i==q)
        {
            for(int j=1;j<=n;j++)
            {
                sz[j]=1;
                p[j]=j;
            }
            vector<pii>order;
            for(int j=1;j<=m;j++)
            {
                if(!change[j]) order.push_back(mp(w[j],j));
            }
            sort(order.begin(),order.end());
            sort(query[2].rbegin(),query[2].rend());
            int cur=order.size()-1;
            for(auto&x:query[2])
            {
                while(cur>=0&&order[cur].fi>=get<0>(x))
                {
                    Union(u[order[cur].se],v[order[cur].se]);
                    cur--;
                }
                for(auto&id:query[1]) tmpw[get<1>(id)]=w[get<1>(id)];
                for(auto&id:query[1]) if(get<2>(id)<get<2>(x)) tmpw[get<1>(id)]=get<0>(id);
                for(auto&id:query[1]) if(tmpw[get<1>(id)]>=get<0>(x)) link(u[get<1>(id)],v[get<1>(id)]);
                go.clear();
                dfs(Find(get<1>(x)));
                for(auto&ver:go)
                {
                    vis[ver]=false;
                    res[get<2>(x)]+=sz[ver];
                }
                for(auto&id:query[1])
                {
                     adj[Find(u[get<1>(id)])].clear();
                     adj[Find(v[get<1>(id)])].clear();
                }
            }
            for(int j=1;j<=m;j++) change[j]=false;
            for(auto&id:query[1]) w[get<1>(id)]=get<0>(id);
            query[1].clear();
            query[2].clear();
        }
    }
    for(int i=1;i<=q;i++) if(res[i]) cout<<res[i]<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...