Submission #558158

#	Time	Username	Problem	Language	Result	Execution time	Memory
558158		hibiki	Bridges (APIO19_bridges)	C++11	100 / 100	2265 ms	32168 KiB

bridges

#include<bits/stdc++.h>
using namespace std;

#define PB push_back

const int sq = 1000;

int n,m,q;

// dsu
int l[50005],sz[50005];
stack<int> stk;

void reset()
{
    iota(l + 1, l + 1 + n, 1);
    fill(sz + 1, sz + 1 + n, 1);
}

int fi(int idx)
{
    while(l[idx] != idx) idx = l[idx];
    return idx;
}

void uni(int a,int b)
{
    a = fi(a), b = fi(b);
    if(a == b) return ;
    if(sz[a] > sz[b]) swap(a,b);
    stk.push(a);
    sz[b] += sz[a];
    l[a] = l[b];
}

void rollback(int x)
{
    while(stk.size() > x)
    {
        int a = stk.top();
        stk.pop();
        sz[l[a]] -= sz[a];
        l[a] = a;
    }
}

int u[100005],v[100005],w[100005];
int ty[100005],x[100005],y[100005],ans[100005];
bool chg[100005];
vector<int> to_join[sq];

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d %d %d",&u[i],&v[i],&w[i]);
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
        scanf("%d %d %d",&ty[i],&x[i],&y[i]);

    for(int l = 1; l <= q; l += sq)
    {
        int r = min(q + 1, l + sq);
        reset();
        fill(chg + 1, chg + 1 + m, false);

        vector<int> ask, upd, unchg;
        for(int i = l; i < r; i++)
        {
            if(ty[i] == 1)
            {
                chg[x[i]] = true;
                upd.PB(i);
            }
            else
                ask.PB(i);
        }

        for(int i = 1; i <= m;i++)
            if(!chg[i])
                unchg.PB(i);

        for(int i = l; i < r; i++)
        {
            if(ty[i] == 1)
                w[x[i]] = y[i];
            else
            {
                to_join[i - l].clear();
                for(int j: upd)
                    if(w[x[j]] >= y[i])
                        to_join[i - l].PB(x[j]);
            }
        }

        sort(ask.begin(), ask.end(), [&](int a,int b) { return y[a] > y[b]; } );
        sort(unchg.begin(), unchg.end(), [&](int a,int b) { return w[a] > w[b]; });

        int ptr = 0;
        for(int i: ask)
        {
            while(ptr < unchg.size() && w[unchg[ptr]] >= y[i])
            {
                uni(u[unchg[ptr]], v[unchg[ptr]]);
                ptr++;
            }
            int prev_sz = stk.size();

            for(int j: to_join[i - l])
                uni(u[j], v[j]);

            ans[i] = sz[fi(x[i])];

            rollback(prev_sz);
        }
    }

    for(int i = 1; i <= q; i++)
        if(ty[i] == 2)
            printf("%d\n",ans[i]);
}

Compilation message (stderr)

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:38:22: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |     while(stk.size() > x)
      |           ~~~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:102:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |             while(ptr < unchg.size() && w[unchg[ptr]] >= y[i])
      |                   ~~~~^~~~~~~~~~~~~~
bridges.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf("%d %d %d",&u[i],&v[i],&w[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
bridges.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scanf("%d %d %d",&ty[i],&x[i],&y[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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