Submission #1098379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098379		vjudge1	Bridges (APIO19_bridges)	C++17	100 / 100	2347 ms	49952 KiB

bridges

// Bolatulu
#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define kanagattandirilmagandiktarinizdan ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define pb push_back
#define pf push_front
#define eb emplace_back
#define ins insert
#define F first
#define S second
#define fx cout << fixed << setprecision(6);
#define md (tl+tr)/2
#define TL v+v, tl,md
#define TR v+v+1, md+1,tr
#define Tl t[v].l, tl,md
#define Tr t[v].r, md+1,tr
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define all(x) (x).begin(), (x).end()
#define int ll
#define cnk(n,k) mod(mod(f[(n)]*binpow(f[(n)-(k)],M-2))*binpow(f[(k)],M-2))
#define cnkf(n,k) mod(mod(f[(n)]*inv[(n)-(k)])*inv[(k)])

using namespace std;

typedef complex<double> cd;

struct mine{int l;int r;int i;};
struct edge{int w;int u;int v;int i;};
struct tree{int l;int r;int val;};

mt19937 RR((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
 
int random(int l, int r){
  return uniform_int_distribution<int>(l, r)(RR);
}

bool cmp(edge a,edge b) {
    if (a.w!=b.w)
        return a.w>b.w;
    return true;
}

int M=998244353;

int mod1(int a,int b=M) {
    if (a<0)
        a=b+a%b;
    return a % b;
}

int binpow(int a,int n,int m=M) {
    a=mod1(a,m);
    if (!n)
        return 1;
    if (n&1)
        return (a * binpow(a,n-1))%m;
    int x = binpow(a,n>>1);
    return (x*x)%m; 
}

const ll INF=1e18+7;
const int N=2e5+7;

int n,m,q,t[N],s[N],c[N],a[N],b[N],e1[N],e2[N],w[N],p[N],sz[N],ans[N],cnt,wc[N];
vector <int> g[N];
bool u[N],h[N];
set <array <int,4>> e;

int find(int v) {
    if (p[v]==v)
        return v;
    return p[v]=find(p[v]);
}

void unite(int u,int v) {
    u=find(u), v=find(v);
    if (u==v)
        return;
    p[v]=u;
    sz[u]+=sz[v];
}

void dfs(int v) {
    u[v]=true;
    cnt+=sz[v];
    for (auto to : g[v]) {
        if (!u[to])
            dfs(to);
    }
}

void upd(int i,int x) {
    auto it=e.find({wc[i],e1[i],e2[i],i});
    if (it!=e.end())
        e.erase(it);
    wc[i]=-x;
    e.insert({wc[i],e1[i],e2[i],i});
}

void solve() {
    cin >> n >> m;
    for (int i=1;i<=m;i++) {
        cin >> e1[i] >> e2[i] >> w[i];
        upd(i,w[i]);
    }
    cin >> q;
    for (int i=0;i<q;i++) {
        cin >> t[i] >> s[i] >> c[i];
    }
    int sq=sqrt(q);
    for (int i=0;i<q;i+=sq) {
        for (int j=1;j<=n;j++) {
            p[j]=j;
            sz[j]=1;
        }
        for (int j=1;j<=m;j++)
            h[j]=true;
        int r=min(q,i+sq);
        vector <pair <int,int>> v;
        set <int> st;
        vector <int> vt;
        for (int j=i;j<r;j++) {
            if (t[j]==1) {
                a[s[j]]=-1;
                h[s[j]]=false;
                st.insert(s[j]);
            }
            else
                v.eb(c[j],j);
        }
        for (auto now : st)
            vt.pb(now);
        sort(all(v));
        reverse(all(v));
        for (int j=1;j<=m;j++) {
            if (a[j]!=-1)
                a[j]=w[j];
            b[j]=w[j];
        }
        for (int j=0;j<i;j++) {
            if (t[j]==1) {
                b[s[j]]=c[j];
                if (a[s[j]]!=-1)
                    a[s[j]]=c[j];
            }
        }
        auto p=e.begin();
        // cout << e.size() << ' ' << (*p)[0] << '\n';
        for (auto now : v) {
            while (p!=e.end() and -(*p)[0]>=now.F) {       
                // cout << (*p)[1] << ' ' << (*p)[2] << ' ' << -(*p)[0] << ' ' << now.F << '\n';
                if (h[(*p)[3]]) {
                    unite((*p)[1],(*p)[2]);
                }
                p++;
            }
            for (int j=i;j<r;j++) {
                if (t[j]==1)
                    a[s[j]]=b[s[j]];
            }
            for (int j=i;j<now.S;j++) {
                if (t[j]==1)
                    a[s[j]]=c[j];
            }
            for (auto cur : st) {
                if (a[cur]<now.F)
                    continue;
                int U=find(e1[cur]),V=find(e2[cur]);
                g[U].pb(V);
                g[V].pb(U);
            }
            cnt=0;
            dfs(find(s[now.S]));
            ans[now.S]=cnt;
            u[find(s[now.S])]=false;
            for (auto cur : vt) {
                if (a[cur]<now.F)
                    continue;
                int U=find(e1[cur]),V=find(e2[cur]);
                g[U].clear();
                g[V].clear();
                u[U]=false;
                u[V]=false;
            }
        }   
        for (int j=i;j<r;j++) {
            if (t[j]==1)
                upd(s[j],c[j]);
        }
        // cout << '\n';
    }
    for (int i=0;i<q;i++) {
        if (t[i]==2)
            cout << ans[i] << '\n';
    }
}   

signed main() {
    /*
    freopen("sequence.in", "r", stdin);
    freopen("sequence.out", "w", stdout);
    */
    // fx
    kanagattandirilmagandiktarinizdan
    int test = 1, count = 1;
    // cin >> test;
    while (test--) {
        // cout << "Case " << count << ":\n";
        solve();
        if (test) {
            cout << '\n';
            count++;
        }
    }
    return 0;
}

// ctrl + shift + p make stress isis__Good isis__Generator

// g++ -std=c++17 (path) -o run
// .\run

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