Submission #302274

#	Time	Username	Problem	Language	Result	Execution time	Memory
302274		vipghn2003	Bridges (APIO19_bridges)	C++14	73 / 100	3082 ms	9440 KiB

bridges

#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];

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 ;
    if(sz[u]>sz[v]) swap(u,v);
    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=500;
    vector<pii>order;
    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;
            }
            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(!order.empty()&&order.back().fi>=get<0>(x))
                {
                    Union(u[order.back().se],v[order.back().se]);
                    order.pop_back();
                }
                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)]);
                dfs(Find(get<1>(x)));
                while(!go.empty())
                {
                    int ver=go.back();
                    go.pop_back();
                    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();
            order.clear();
        }
    }
    for(int i=1;i<=q;i++) if(res[i]) cout<<res[i]<<'\n';
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:74:17: warning: unused variable 'cur' [-Wunused-variable]
   74 |             int cur=order.size()-1;
      |                 ^~~

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 0 / 27