Submission #1175954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175954		son2008	Bridges (APIO19_bridges)	C++20	0 / 100	3095 ms	4604 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
#define task "task"
#define ii pair<int,int>
#define fi first
#define se second
//#define int long long
#define ll long long
#define ld double
#define mp make_pair
#define lg2 30
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define base 29
#define eps 1e-8
int dx[]= {0LL,0LL,1,-1,1,1,-1,-1};
int dy[]= {1,-1,0LL,0LL,1,-1,1,-1};
const int maxn=1e5+1,S=317;
const int mod=1e9+7;
int n,m,Q,mask[maxn],lab[maxn],vis[maxn],ans[maxn];
struct pt
{
    int u,v,d;
};
struct pt1
{
    int t,u,d;
};
pt a[maxn];
pt1 q[maxn];

stack<ii>roll;
void init()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i].u>>a[i].v>>a[i].d;
    }
    cin>>Q;
    for(int i=1;i<=Q;i++)
    {
        cin>>q[i].t>>q[i].u>>q[i].d;
    }
}
int acs(int u)
{
    return lab[u]<0?u:acs(lab[u]);
}
void join1(int u,int v,int type)
{
    u=acs(u),v=acs(v);
    if(u==v)return;
    if(lab[u]>lab[v])swap(u,v);
    if(type)roll.push({v,lab[v]});
    lab[u]+=lab[v];
    lab[v]=u;
}
void rollback()
{
    while(!roll.empty())
    {
        ii tmp=roll.top();
        roll.pop();
        lab[lab[tmp.fi]]-=tmp.se;
        lab[tmp.fi]=tmp.se;
    }
}
void process()
{
    for(int st=1;st<=Q;st+=S)
    {
        int en=min(Q,st+S-1);
        vector<int>tv2,no_join,join;
        for(int i=1;i<=en;i++)
        {
            if(q[i].t==1)
            {
                mask[q[i].u]=1;
            }
            else
            {
                tv2.push_back(i);
            }
        }
        for(int i=1;i<=m;i++)
        {
            if(!mask[i])
            {
                no_join.push_back(i);
            }
            else
            {
                join.push_back(i);
            }
        }
        sort(tv2.begin(),tv2.end(),[](const int &x,const int &y)-> bool
        {
            return q[x].d>q[y].d;
        });
        sort(no_join.begin(),no_join.end(),[](const int &x,const int &y)-> bool
        {
            return a[x].d>a[y].d;
        });
        memset(lab,-1,sizeof(lab));
        int j=0;
        for(int i=0;i<tv2.size();i++)
        {
            while(j<no_join.size()&&a[no_join[j]].d>=q[tv2[i]].d)
            {
                join1(a[no_join[j]].u,a[no_join[j]].v,0);
                j++;
            }
            for(int z=st;z<tv2[i];z++)
            {
                if(q[z].t==1)
                {
                    vis[q[z].u]=z;
                }
            }
            for(int x:join)
            {
                if(vis[x])
                {
                    if(q[vis[x]].d>=q[tv2[i]].d)
                    {
                        join1(a[x].u,a[x].v,1);
                    }
                }
                else
                {
                    if(a[x].d>=q[tv2[i]].d)
                    {
                        join1(a[x].u,a[x].v,1);
                    }
                }
            }
            ans[tv2[i]]=-lab[acs(q[tv2[i]].u)];
            rollback();
            for(int z=st;z<tv2[i];z++)
            {
                if(q[z].t==1)
                {
                    vis[q[z].u]=0;
                }
            }
        }
        for(int i=st;i<=en;i++)
        {
            if(q[i].t==1)
            {
                mask[q[i].u]=0;
                a[q[i].u].d=q[i].d;
            }
        }
    }
    for(int i=1;i<=Q;i++)
    {
        if(q[i].t==2)
        cout<<ans[i]<<'\n';
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    init();
    process();
    cerr <<endl<< "TIME : " << clock() * 0.001 << "s" << endl ;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:170:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:171:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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