Submission #399764

#	Time	Username	Problem	Language	Result	Execution time	Memory
399764		MarcoMeijer	Bridges (APIO19_bridges)	C++14	100 / 100	2979 ms	12320 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
 
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e18
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }
 
// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const vector<T>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);}
template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }
template<class H> void OUTLS(const H& h) {OUTL(h); }
template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); }
 
// dp
template<class T> bool ckmin(T&a, T&b) { bool bl = a > b; a = min(a,b); return bl;}
template<class T> bool ckmax(T&a, T&b) { bool bl = a < b; a = max(a,b); return bl;}
 
void program();
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    program();
}
 
 
//===================//
//   begin program   //
//===================//
 
const int MX = 1e5+10;
const int N = (1<<20);
const int SQ = 700;

int n, m;
int u[MX], v[MX], d[MX], tempD[MX];
int q;
int t[MX], b[MX], nd[MX], s[MX], w[MX];
int ans[MX];

// dsu
int p[MX], sz[MX];
stack<int> stck;
void buildDSU(int dsuSize) {
    RE(i,dsuSize) p[i]=i, sz[i]=1;
    while(!stck.empty()) stck.pop();
}
int getSet(int i) {return i==p[i]?i:getSet(p[i]);}
bool isSameSet(int i, int j) {return getSet(i)==getSet(j);}
void unionSet(int i, int j) {
    i = getSet(i); j = getSet(j);
    if(i != j) {
        if(sz[i] < sz[j]) swap(i,j);
        sz[i] = sz[i] + sz[j];
        p[j] = i;
        stck.push(j);
    } else {
        stck.push(-1);
    }
}
void unionUndo() {
    int u = stck.top(); stck.pop();
    if(u == -1) return;
    sz[p[u]] -= sz[u];
    p[u] = u;
}

bitset<MX> used;
vi inBlock[SQ];

void program() {
    IN(n,m);
    RE(i,m) IN(u[i],v[i],d[i]);
    IN(q);
    RE(i,q) {
        IN(t[i]);
        if(t[i] == 1) IN(b[i],nd[i]), b[i]--;
        if(t[i] == 2) IN(s[i],w[i]);
    }

    RE(i,q) inBlock[i/SQ].pb(i);

    RE(cb,SQ) {
        if(inBlock[cb].empty()) break;

        used.reset();
        vi impEdges;
        vi changes;
        vii queries;
        FOR(i,inBlock[cb]) {
            if(t[i] == 1) {
                impEdges.pb(b[i]);
                used[b[i]] = 1;
                changes.pb(i);
            }
            if(t[i] == 2) queries.pb({w[i],i});
        }
        sort(all(queries),greater<ii>());

        viii edges;
        RE(i,m) if(!used[i]) edges.pb({d[i],u[i],v[i]});
        sort(all(edges),greater<iii>());

        buildDSU(n+1);
        int cq = 0;
        auto answerQuery = [&](int i) {
            FOR(u,impEdges) tempD[u] = d[u];
            FOR(j,changes) {
                if(j >= i) break;
                if(t[j] == 1) tempD[b[j]] = nd[j];
            }
            int undos = 0;
            FOR(j,impEdges)
                if(tempD[j] >= w[i])
                    unionSet(u[j],v[j]), undos++;
            ans[i] = sz[getSet(s[i])];
            RE(_,undos)
                unionUndo();
        };
        FOR(p,edges) {
            int cd, u, v;
            tie(cd,u,v) = p;
            while(cq != queries.size() && queries[cq].fi > cd)
                answerQuery(queries[cq++].se);
            unionSet(u,v);
        }
        while(cq != queries.size())
            answerQuery(queries[cq++].se);

        // update distances for next block
        FOR(i,inBlock[cb]) if(t[i] == 1) d[b[i]] = nd[i];
    }

    RE(i,q) if(t[i] == 2) OUTL(ans[i]);
}

Compilation message (stderr)

bridges.cpp: In function 'void program()':
bridges.cpp:154:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |             while(cq != queries.size() && queries[cq].fi > cd)
      |                   ~~~^~~~~~~~~~~~~~~~~
bridges.cpp:158:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |         while(cq != queries.size())
      |               ~~~^~~~~~~~~~~~~~~~~

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