제출 #724670

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
724670		n0sk1ll	다리 (APIO19_bridges)	C++14	13 / 100	113 ms	20892 KiB

bridges

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

set<pair<int,pii>> prim;
pair<int,pii> ed[1000003];

pair<int,pii> qry[1000003];

int up[5000003];
int Up(int x)
{
    if (up[x]<0) return x;
    return up[x]=Up(up[x]);
}

void dsu(int a, int b)
{
    a=Up(a),b=Up(b); if (a==b) return;
    if (up[a]<up[b]) swap(a,b);
    up[b]+=up[a],up[a]=b;
}

void rebuild(int n)
{
    fff(i,1,n) up[i]=-1;
}

void solvebrut(int n, int m, int q)
{
    fff(i,1,q)
    {
        if (qry[i].xx==1)
        {
            ed[qry[i].yy.xx].xx=qry[i].yy.yy;
        }
        else
        {
            rebuild(n);
            fff(j,1,m) if (ed[j].xx>=qry[i].yy.yy) dsu(ed[j].yy.xx,ed[j].yy.yy);
            cout<<-up[Up(qry[i].yy.xx)]<<"\n";
        }
    }
}

int ans[1000005];
void solvenoupdates(int n, int m, int q)
{
    rebuild(n);
    
    vector<pair<pii,int>> offline;
    fff(i,1,q) offline.pb({qry[i].yy,i});
    sort(all(offline));

    while (!prim.empty())
    {
        while (!offline.empty() && offline.back().xx.xx>(*prev(prim.end())).xx)
        {
            ans[offline.back().yy]=-up[offline.back().xx.yy];
            offline.popb();
        }
        dsu((*prev(prim.end())).yy.xx,(*prev(prim.end())).yy.yy);
        prim.erase(prev(prim.end()));
    }

    while (!offline.empty())
    {
        ans[offline.back().yy]=-up[offline.back().xx.yy];
        offline.popb();
    }

    fff(i,1,q) cout<<ans[i]<<"\n";
}

int main()
{
    FAST;

    int n,m; cin>>n>>m;
    fff(i,1,m)
    {
        cin>>ed[i].yy.xx>>ed[i].yy.yy>>ed[i].xx;
        prim.insert(ed[i]);
    }

    int q; cin>>q;
    fff(i,1,q) cin>>qry[i].xx>>qry[i].yy.xx>>qry[i].yy.yy;

    if (n<=1000 && m<=1000 && q<=10000) solvebrut(n,m,q);
    else solvenoupdates(n,m,q);
}

//Note to self: Check for overflow

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