Submission #336456

#	Time	Username	Problem	Language	Result	Execution time	Memory
336456		greedeb	Bridges (APIO19_bridges)	C++14	59 / 100	3065 ms	9444 KiB

bridges

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

using namespace std;

#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define endl '\n'

using pii = pair<int, int>;
#define Fir first
#define Sec second

struct Edge {
    int a, b, cost;

    bool operator<(const Edge &cp) const {
        return cost > cp.cost;
    }
};
vector<Edge> e, const_e;
vector<pii> dynamic_e;

bool skp[100000];

struct Query{
    int idx;
    int q, a, b;
    int res;
    bool operator<(const Query& cp) const{
        return b > cp.b;
    }
};
vector<Query> q, res_q, dynamic_q;

int root[50001];
int d_root[50001];
int sz[50001];
int dsz[50001];

int GetRoot(int x){
    return root[x] == x ? x : root[x] = GetRoot(root[x]);
}
int GetDRoot(int x){
    return d_root[x] == x ? x : d_root[x] = GetDRoot(d_root[x]);
}
void Union(int a, int b){
    int aRoot = GetRoot(a);
    int bRoot = GetRoot(b);
    if(aRoot == bRoot)
        return;
    sz[bRoot] += sz[aRoot];
    root[GetRoot(a)] = GetRoot(b);
}
void D_Union(int a, int b){
    int adRoot = GetDRoot(GetRoot(a));
    int bdRoot = GetDRoot(GetRoot(b));
    if(adRoot == bdRoot)
        return;
    dsz[adRoot] += dsz[bdRoot];
    d_root[bdRoot] = adRoot;
}

int main(){
    fastio;
    int n, m;

    cin >> n >> m;
    e.resize(m);
    for(int i = 0; i < m; i++){
        cin >> e[i].a >> e[i].b >> e[i].cost;
    }

    int Q;
    cin >> Q;;
    q.resize(Q);
    for(int i = 0; i < Q; i++){
        q[i].idx = i;
        cin >> q[i].q >> q[i].a >> q[i].b;
        if(q[i].q == 1)
            q[i].a--;
    }

    for(int s = 0; s * 350 < Q; s++){
        int st = s * 350;
        int ed = min((s + 1) * 350, Q);

        const_e.clear();
        dynamic_e.clear();
        res_q.clear();
        dynamic_q.clear();

        fill(sz, sz + 50001, 1);
        for(int i = st; i < ed; i++){
            if(q[i].q == 1){
                dynamic_q.push_back(q[i]);
                skp[q[i].a] = true;
            }
            else
                res_q.push_back(q[i]);
        }
        for(int i = 0; i < m; i++){
            if(skp[i])
                dynamic_e.emplace_back(i, e[i].cost);
            else
                const_e.push_back(e[i]);
        }
        sort(const_e.begin(), const_e.end());
        sort(res_q.begin(), res_q.end());
        for(int i = 1; i <= n; i++)
            root[i] = d_root[i] = i;

        int add = 0;

        for(auto& r : res_q){
            while(add < const_e.size() && const_e[add].cost >= r.b){
                Union(const_e[add].a, const_e[add].b);
                add++;
            }
            d_root[GetRoot(r.a)] = GetRoot(r.a);
            dsz[GetDRoot(GetRoot(r.a))] = sz[GetRoot(r.a)];
            for(auto& p : dynamic_e){
                e[p.Fir].cost = p.Sec;
                int ar = GetRoot(e[p.Fir].a);
                int br = GetRoot(e[p.Fir].b);
                d_root[ar] = ar;
                d_root[br] = br;
                dsz[ar] = sz[ar];
                dsz[br] = sz[br];
            }
            for(auto& dq : dynamic_q){
                if(dq.idx < r.idx)
                    e[dq.a].cost = dq.b;
                else
                    break;
            }
            for(auto& p : dynamic_e){
                if(e[p.Fir].cost >= r.b)
                    D_Union(e[p.Fir].a, e[p.Fir].b);
            }
            q[r.idx].res = dsz[GetDRoot(GetRoot(r.a))];
        }
        for(auto& dq : dynamic_q){
            e[dq.a].cost = dq.b;
            skp[dq.a] = false;
        }
    }
    for(int i = 0; i < Q; i++){
        if(q[i].q == 2)
            cout << q[i].res << endl;
    }
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:115:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |             while(add < const_e.size() && const_e[add].cost >= r.b){
      |                   ~~~~^~~~~~~~~~~~~~~~

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