Submission #733198

#	Time	Username	Problem	Language	Result	Execution time	Memory
733198		Magikarp4000	Bridges (APIO19_bridges)	C++17	27 / 100	3095 ms	11964 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;
#pragma gcc optimize("O3")

struct Query {
    int idx,x,y;
};

const int MAXN = 1e5+1, BLOCK = 400;
int n,m,q;
int p[MAXN], sz[MAXN], res[MAXN];
vector<pair<PII,PII>> e;
vector<Query> qu1, qu2;
US<int> z;
int ans, mp[MAXN];
set<PII> h;
vector<PII> edges;
int wt[MAXN];

int finds(int a) {
  if (p[a] != a) p[a] = finds(p[a]);
  return p[a];
}

void unite(int a, int b) {
  a = finds(a);
  b = finds(b);
  if (a != b) {
    if (sz[a] < sz[b]) swap(a,b);
    p[b] = a;
    sz[a] += sz[b];
  }
}

void dfs(int s, UM<int,US<int>>& v) {
    if (z.count(s)) return;
    z.insert(s);
    ans += sz[s];
    FORX(u,v[s]) {
        int to = finds(e[u].S.F) == s ? finds(e[u].S.S) : finds(e[u].S.F);
        dfs(to,v);
    }
}

bool cmp(const Query& a, const Query& b) {
    return a.y > b.y;
}

signed main() {
    OPTM;
    cin >> n >> m;
    FOR(i,0,m) {
        int a,b,w; cin >> a >> b >> w;
        e.PB({{w,i},{a,b}});
        h.insert({-w,i});
        edges.PB({a,b});
        wt[i] = w;
    }
    sort(ALL(e),greater<pair<PII,PII>>());
    
    cin >> q;
    int i = 0;
    while (i < q) {
        int bruh = 0;
        FORX(u,h) {
            e[bruh] = {{-u.F,u.S},edges[u.S]};
            bruh++;
        }
        FOR(l,0,m) mp[e[l].F.S] = l;
        qu1.clear(); qu2.clear();
        FOR(l,1,n+1) {
            p[l] = l;
            sz[l] = 1;
        }
        int j = 0;
        US<int> vis;
        while (j < BLOCK && i < q) {
            int t,s,w; cin >> t >> s >> w;
            if (t == 1) {
                qu1.PB({i,s-1,w});
                vis.insert(s-1);
            }
            else qu2.PB({i,s,w});
            j++; i++;
        }
        sort(ALL(qu2),cmp);
        vector<pair<int,PII>> e1;
        FOR(j,0,m) if (!vis.count(e[j].F.S)) e1.PB({e[j].F.F,{e[j].S}});
        int en = e1.size();
        int q1n = qu1.size(), q2n = qu2.size();
        int k = 0;
        FOR(j,0,q2n) {
            while (k < en && e1[k].F >= qu2[j].y) {
                unite(e1[k].S.F, e1[k].S.S);
                k++;
            }
            //ans = sz[finds(qu2[j].x)];
            UM<int,US<int>> v;
            z.clear();
            ans = 0;
            
            FOR(l,0,q1n) {
                int a = e[mp[qu1[l].x]].S.F, b = e[mp[qu1[l].x]].S.S;
                int w = e[mp[qu1[l].x]].F.F;
                if (e[mp[qu1[l].x]].F.F >= qu2[j].y) {
                    v[finds(a)].insert(mp[qu1[l].x]);
                    v[finds(b)].insert(mp[qu1[l].x]);
                }
            }
            FOR(l,0,q1n) {
                if (qu1[l].idx > qu2[j].idx) continue;
                int pos = mp[qu1[l].x];
                int a = e[pos].S.F, b = e[pos].S.S, w = qu1[l].y;
                int na = finds(a), nb = finds(b);
                if (w >= qu2[j].y) {
                    v[na].insert(pos);
                    v[nb].insert(pos);
                }
                else {
                    if (v[na].count(pos)) {
                        v[na].erase(pos);
                        v[nb].erase(pos);
                    }
                }
            }
            
            dfs(finds(qu2[j].x),v);
            res[qu2[j].idx] = ans;
            // FORX(u,v) {
            //     cout << u.F << ": ";
            //     FORX(y,u.S) cout << y << ' ';
            //     cout << ln;
            // }
        }
        // FOR(i,1,n+1) cout << finds(i) << ' ';
        // cout << ln;
        FOR(l,0,q1n) {
            int pos = qu1[l].x;
            h.erase({-wt[pos],pos});
            wt[pos] = qu1[l].y;
            h.insert({-wt[pos],pos});
        }
    }
    FOR(i,0,q) if (res[i]) cout << res[i] << ln;
}

Compilation message (stderr)

bridges.cpp:24: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
   24 | #pragma gcc optimize("O3")
      | 
bridges.cpp: In function 'int main()':
bridges.cpp:125:21: warning: unused variable 'w' [-Wunused-variable]
  125 |                 int w = e[mp[qu1[l].x]].F.F;
      |                     ^

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