Submission #130167

#	Time	Username	Problem	Language	Result	Execution time	Memory
130167		ae04071	Bridges (APIO19_bridges)	C++11	100 / 100	2937 ms	11676 KiB

bridges

#include <bits/stdc++.h>
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using namespace std;
using lli = long long;
using pii = pair<int,int>;

struct edge{
    int u,v,w,i,c;
    int l,r;
    bool operator<(const edge &rhs)const {
        return w<rhs.w;
    }
}arr[200000];
struct qd{
    int t,a,b;
    bool operator<(const qd &rhs)const {
        return b<rhs.b;
    }
}qa[100000];

int n,m,q;

struct dsu{
    int pa[50001],sz[50001],tp[50001],ts[50001],tf[50001];
    int ti;
    void init() {
        for(int i=1;i<=n;i++) pa[i]=i, sz[i]=1, tf[i]=-1;
    }
    int find(int cur) {
        return cur==pa[cur] ? cur : pa[cur] = find(pa[cur]);
    }
    void merge(int u,int v) {
        u = find(u); v=find(v);
        if(u!=v) {
            pa[v]=u; sz[u]+=sz[v];
        }
    }
    void tcheck(int cur) {
        if(tf[cur]!=ti) tf[cur]=ti, tp[cur]=pa[cur], ts[cur]=sz[cur];
    }
    int tfind(int cur) {
        tcheck(cur);
        return cur==tp[cur] ? cur : tp[cur] = tfind(tp[cur]);
    }
    void tmerge(int u,int v) {
        u=tfind(u), v=tfind(v);
        if(u!=v) {
            tp[v]=u;
            ts[u] += ts[v];
        }
    }
    int tgetsz(int cur) {
        cur=tfind(cur);
        return ts[cur];
    }
}ds;
int ans[100000],pr[100000];
int main() {
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++) {
        scanf("%d%d%d",&arr[i].u,&arr[i].v,&arr[i].w);
        arr[i].w = -arr[i].w;
        arr[i].i = i; arr[i].c = -1;
    }

    scanf("%d",&q);
    for(int i=0;i<m;i++) arr[i].l=-1,arr[i].r=q, pr[i] = i;
    for(int i=0;i<q;i++) {
        scanf("%d%d%d",&qa[i].t,&qa[i].a,&qa[i].b);
        qa[i].b = -qa[i].b;
        if(qa[i].t==1) {
            qa[i].a--;

            int idx = pr[qa[i].a];
            arr[m] = arr[idx];
            arr[m].w = qa[i].b;
            arr[idx].r = i;
            arr[m].l = i;

            pr[qa[i].a] = m++;
        }
    }
    sort(arr,arr+m);

    const int B = 500;
    for(int bi=0;bi*B<q;bi++) {
        vector<pair<qd,int>> a2;
        vector<edge> a1;
        for(int i=bi*B;i<min(bi*B+B, q);i++) {
            if(qa[i].t==2) a2.push_back({qa[i], i});
        }
        sort(a2.begin(),a2.end());

        int s=bi*B, e=min(bi*B+B,q);
        for(int i=0;i<m;i++) {
            if((s<=arr[i].l && arr[i].l<e) || (s<=arr[i].r && arr[i].r<e)) arr[i].c=bi,a1.push_back(arr[i]);
        }

        int ei=0;
        ds.init();
        for(int i=0;i<sz(a2);i++) {
            ds.ti=i;
            for(;ei<m && arr[ei].w <= a2[i].fi.b; ei++) if(arr[ei].c!=bi && arr[ei].l<s && arr[ei].r>=e) {
                ds.merge(arr[ei].u, arr[ei].v);
            }
            for(int j=0;j<sz(a1);j++) {
                if(a1[j].l<=a2[i].se && a2[i].se<=a1[j].r && a1[j].w <= a2[i].fi.b) ds.tmerge(a1[j].u,a1[j].v); 
            }
            ans[a2[i].se] = ds.tgetsz(a2[i].fi.a);
        }
    }

    for(int i=0;i<q;i++) if(qa[i].t==2) printf("%d\n",ans[i]);
    
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
bridges.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&arr[i].u,&arr[i].v,&arr[i].w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
bridges.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&qa[i].t,&qa[i].a,&qa[i].b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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