Submission #1098434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098434		Bolatulu	Bridges (APIO19_bridges)	C++14	30 / 100	3032 ms	21924 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 u;int v;int w;};
struct tree{int l;int r;int val;};

bool cmp(edge a,edge b) {
    return a.w>b.w;
}

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);
}

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;
vector <int> g[N];
bool u[N];

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 solve() {
    cin >> n >> m;
    for (int i=1;i<=m;i++) {
        cin >> e1[i] >> e2[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;
        }
        int r=min(q,i+sq);
        vector <pair <int,int>> v;
        vector <edge> e;
        set <int> st;
        vector <int> vt;
        for (int j=i;j<r;j++) {
            if (t[j]==1) {
                a[s[j]]=-1;
                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];
            }
        }
        for (int j=1;j<=m;j++) {
            if (a[j]!=-1)
                e.pb({e1[j],e2[j],a[j]});
        }
        sort(all(e),cmp);
        int p=0;
        for (auto now : v) {
            while (p<e.size() and e[p].w>=now.F) {
                unite(e[p].u,e[p].v);
                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 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

Compilation message (stderr)

bridges.cpp: In function 'void solve()':
bridges.cpp:144:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |             while (p<e.size() and e[p].w>=now.F) {
      |                    ~^~~~~~~~~

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