제출 #933894

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
933894		Hanksburger	다리 (APIO19_bridges)	C++17	100 / 100	1885 ms	17420 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
int U[100005], V[100005], W[100005], t[100005], x[100005], y[100005], ans[100005], par[50005], sz[50005];
vector<pair<pair<int, int>, pair<int, int> > > update;
vector<int> changed[100005];
void add(int u, int v, int ok)
{
    while (par[u]!=u)
        u=par[u];
    while (par[v]!=v)
        v=par[v];
    if (u==v)
        return;
    if (ok)
        update.push_back({{u, v}, {sz[u], sz[v]}});
    if (sz[u]<sz[v])
    {
        par[u]=v;
        sz[v]+=sz[u];
    }
    else
    {
        par[v]=u;
        sz[u]+=sz[v];
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, q;
    cin >> n >> m;
    for (int i=1; i<=m; i++)
        cin >> U[i] >> V[i] >> W[i];
    cin >> q;
    for (int i=1; i<=q; i++)
        cin >> t[i] >> x[i] >> y[i];
    for (int i=1; i<=q; i+=1000)
    {
        int l=i, r=min(i+999, q);
        for (int j=1; j<=m; j++)
            changed[j].clear();
        for (int j=l; j<=r; j++)
            if (t[j]==1)
                changed[x[j]].push_back(j);
        vector<pair<int, pair<int, int> > > vec1;
        vector<pair<int, int> > vec0[1005];
        for (int j=1; j<=m; j++)
        {
            if (changed[j].empty())
                vec1.push_back({W[j], {U[j], V[j]}});
            else
            {
                for (int k=l; k<changed[j][0]; k++)
                    if (t[k]==2 && y[k]<=W[j])
                    {
                        vec0[k-l].push_back({U[j], V[j]});
                    //    cout << "add " << k-l << ' ' << U[j] << ' ' << V[j] << '\n';
                    }
                int cnt=changed[j].size();
                for (int k=0; k<=cnt-2; k++)
                    for (int kk=changed[j][k]+1; kk<changed[j][k+1]; kk++)
                    {
                        if (t[kk]==2 && y[kk]<=y[changed[j][k]])
                        {
                            vec0[kk-l].push_back({U[j], V[j]});
                        //    cout << "add " << kk-l << ' ' << U[j] << ' ' << V[j] << '\n';
                        }
                    }
                for (int k=changed[j][cnt-1]; k<=r; k++)
                    if (t[k]==2 && y[k]<=y[changed[j][cnt-1]])
                    {
                        vec0[k-l].push_back({U[j], V[j]});
                    //    cout << "add " << k-l << ' ' << U[j] << ' ' << V[j] << '\n';
                    }
                W[j]=y[changed[j][cnt-1]];
            }
        }
        vector<pair<int, pair<int, int> > > qry;
        for (int j=0; j<vec1.size(); j++)
            qry.push_back({vec1[j].first, {1, j}});
        for (int j=l; j<=r; j++)
            if (t[j]==2)
                qry.push_back({y[j], {0, j}});
        sort(qry.begin(), qry.end());
        for (int j=1; j<=n; j++)
            par[j]=j, sz[j]=1;
        for (int j=qry.size()-1; j>=0; j--)
        {
        //    cout << "qry " << j << ' ' << qry[j].second.first << ' ' << qry[j].second.second << '\n';
            int ind=qry[j].second.second;
            if (qry[j].second.first)
                add(vec1[ind].second.first, vec1[ind].second.second, 0);
            else
            {
                for (int k=0; k<vec0[ind-l].size(); k++)
                    add(vec0[ind-l][k].first, vec0[ind-l][k].second, 1);
                int cur=x[ind];
                while (par[cur]!=cur)
                    cur=par[cur];
                ans[ind]=sz[cur];
                for (int k=update.size()-1; k>=0; k--)
                {
                    par[update[k].first.first]=update[k].first.first;
                    par[update[k].first.second]=update[k].first.second;
                    sz[update[k].first.first]=update[k].second.first;
                    sz[update[k].first.second]=update[k].second.second;
                }
                update.clear();
            /*    cout << "par: ";
                for (int k=1; k<=n; k++)
                    cout << par[k] << ' ';
                cout << '\n';
                cout << "size: ";
                for (int k=1; k<=n; k++)
                    cout << sz[k] << ' ';
                cout << '\n'; */
            }
        }
    }
    for (int i=1; i<=q; i++)
        if (t[i]==2)
            cout << ans[i] << '\n';
}

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

bridges.cpp: In function 'int main()':
bridges.cpp:81:24: 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]
   81 |         for (int j=0; j<vec1.size(); j++)
      |                       ~^~~~~~~~~~~~
bridges.cpp:97:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |                 for (int k=0; k<vec0[ind-l].size(); k++)
      |                               ~^~~~~~~~~~~~~~~~~~~

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