제출 #645995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
645995		Tenis0206	다리 (APIO19_bridges)	C++11	100 / 100	2123 ms	11288 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

const int bsize = 1000;

struct eveniment
{
    int tip,poz,val;
};

int n,m,q;

pair<int,int> e[100005];
int c[100005];
int new_c[100005];

bool ch[100005];

int rez[100005];

int t[100005];
int rang[100005];

stack<pair<int,int>> st;

int reprezentant(int nod)
{
    if(nod==t[nod])
    {
        return nod;
    }
    return reprezentant(t[nod]);
}

void uneste(int x, int y)
{
    x = reprezentant(x);
    y = reprezentant(y);
    st.push({x,y});
    if(x==y)
    {
        return;
    }
    if(rang[x] > rang[y])
    {
        t[y] = x;
        rang[x] += rang[y];
    }
    else
    {
        t[x] = y;
        rang[y] += rang[x];
    }
}

void remove_last()
{
    int x = st.top().first;
    int y = st.top().second;
    st.pop();
    if(x==y)
    {
        return;
    }
    if(x==t[y])
    {
        t[y] = y;
        rang[x] -= rang[y];
    }
    else
    {
        t[x] = x;
        rang[y] -= rang[x];
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y>>c[i];
        e[i] = {x,y};
    }
    for(int i=1;i<=n;i++)
    {
        t[i] = i;
        rang[i] = 1;
    }
    cin>>q;
    vector<eveniment> eves;
    eves.push_back(eveniment{0,0,0});
    for(int i=1;i<=q;i++)
    {
        eveniment x;
        cin>>x.tip>>x.poz>>x.val;
        eves.push_back(x);
    }
    for(int l=1;l<=q;l+=bsize)
    {
        int r = min(q,l + bsize - 1);
        vector<pair<pair<int,int>,int>> queries;
        vector<pair<pair<int,int>,int>> sp_upd;
        vector<pair<int,pair<int,int>>> upd;
        for(int i=l;i<=r;i++)
        {
            if(eves[i].tip==2)
            {
                queries.push_back({{eves[i].val,eves[i].poz},i});
            }
            else
            {
                ch[eves[i].poz] = true;
                sp_upd.push_back({{eves[i].poz, eves[i].val},i});
            }
        }
        for(int i=1;i<=m;i++)
        {
            if(!ch[i])
            {
                upd.push_back({c[i],{e[i].first,e[i].second}});
            }
            ch[i] = false;
        }
        sort(upd.begin(),upd.end(),greater<pair<int,pair<int,int>>>());
        sort(queries.begin(),queries.end(),greater<pair<pair<int,int>,int>>());
        int poz = 0;
        for(auto it : queries)
        {
            while(poz<upd.size() && upd[poz].first >= it.first.first)
            {
                uneste(upd[poz].second.first,upd[poz].second.second);
                ++poz;
            }
            int cnt = 0;
            for(auto edge : sp_upd)
            {
                if(edge.second <= it.second)
                {
                    new_c[edge.first.first] = edge.first.second;
                }
            }
            for(auto edge : sp_upd)
            {
                if(new_c[edge.first.first]==0)
                {
                    if(c[edge.first.first] >= it.first.first)
                    {
                        uneste(e[edge.first.first].first,e[edge.first.first].second);
                        ++cnt;
                    }
                    continue;
                }
                if(new_c[edge.first.first] >= it.first.first)
                {
                    uneste(e[edge.first.first].first,e[edge.first.first].second);
                    ++cnt;
                }
            }
            for(auto edge : sp_upd)
            {
                new_c[edge.first.first] = 0;
            }
            rez[it.second] = rang[reprezentant(it.first.second)];
            while(cnt)
            {
                remove_last();
                --cnt;
            }
        }
        while(!st.empty())
        {
            remove_last();
        }
        for(int i=l;i<=r;i++)
        {
            if(eves[i].tip==1)
            {
                c[eves[i].poz] = eves[i].val;
            }
        }
    }
    for(int i=1;i<=q;i++)
    {
        if(eves[i].tip==2)
        {
            cout<<rez[i]<<'\n';
        }
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp: In function 'int main()':
bridges.cpp:134:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |             while(poz<upd.size() && upd[poz].first >= it.first.first)
      |                   ~~~^~~~~~~~~~~

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