Submission #132737

#	Time	Username	Problem	Language	Result	Execution time	Memory
132737		icypiggy	Bridges (APIO19_bridges)	C++14	44 / 100	3039 ms	12348 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

const int n_max = 50100;
const int m_max = 1e5+100;
int parent[n_max];
int sz[n_max];
vector<int> adj[n_max];
bitset<n_max> visited;
bitset<n_max> deactivate;

int findset(int x) {
    return (parent[x]==x ? x : parent[x] = findset(parent[x]));
}
void onion(int x, int y) {
    x = findset(x);
    y = findset(y);

    if(x!=y) {
        if(sz[x]>sz[y]) {
            swap(x,y);
        }
        sz[y] += sz[x];
        parent[x] = y;
    }
}
struct edge {
    int u,v,w;
    edge() : u(0), v(0), w(0) {}
    edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {}

};
vector<edge> edgelist;
struct cmp {
    bool operator()(int a, int b) {
        return (edgelist[a].w > edgelist[b].w || (edgelist[a].w==edgelist[b].w && a<b));
    }
};

int wt_new[m_max];
set<int, cmp> edgeset;
vector<pair<int, pair<int,int>>> queries;
pair<int,int> answer_query(int query_w, int starting, int idx) { // index of the query
    vector<int> modified;
    for(auto p: queries) {
        if(p.first==1)
            wt_new[p.second.first] = -1; // reset all the new weights
    }
    for(int i=0; i<idx; i++) {
        if(queries[i].first==1) {
            wt_new[queries[i].second.first] = queries[i].second.second; // update accordingly
        }
    }
    // now all the weights are correct

    // now add them to adj list
    for(auto p: queries) {
        if(p.first==1) {
            int edge_idx = p.second.first;
            int wt = (wt_new[edge_idx]==-1 ? edgelist[edge_idx].w : wt_new[edge_idx]);

            int u1 = findset(edgelist[edge_idx].u);
            int v1 = findset(edgelist[edge_idx].v);
            if(u1!=v1 && wt>=query_w) {
                adj[u1].push_back(v1);
                adj[v1].push_back(u1);
                modified.push_back(u1);
                modified.push_back(v1);
            }
        }
    }

    starting = findset(starting);
    modified.push_back(starting);
    visited[starting] = true;
    queue<int> bfs;
    bfs.push(starting);
    int ans = sz[starting];
    while(!bfs.empty()) {
        int next = bfs.front();
        bfs.pop();
        for(int i: adj[next]) {
            assert(parent[i]==i);
            if(!visited[i]) {
                visited[i] = true;
                ans += sz[i];
                bfs.push(i);
            }
        }
    }
    for(int i: modified) {
        adj[i].clear();
        visited[i] = false;
    }
    visited[starting] = false;
    return make_pair(idx, ans);
}
void clear_queries(int n) {
    // preprocessing
    vector<pair<pair<int, int>, int>> to_ans; // weight, starting, idx
    for(int i=0; i<=n; i++) {
        assert(adj[i].empty());
        parent[i] = i;
        sz[i] = 1;
        assert(!visited[i]);
    }

    for(int i=0; i<queries.size(); i++) {
        auto p = queries[i];
        if(p.first==1) {
            int edge_idx = p.second.first;
            edgeset.erase(edge_idx);
        } else {
            to_ans.push_back(make_pair(queries[i].second, i));
        }
    }

    sort(to_ans.begin(), to_ans.end(), greater<pair<pair<int, int>, int>>());

    // actually answer the queries
    vector<pair<int,int>> answers;
    auto it = edgeset.begin();
    for(auto &q: to_ans) {
        while(it!=edgeset.end() && edgelist[*it].w >= q.first.first) {
            onion(edgelist[*it].u, edgelist[*it].v);
            it++;
        }
        answers.push_back(answer_query(q.first.first, q.first.second, q.second));
    }
    sort(answers.begin(), answers.end());
    for(auto &pp: answers) {
        cout << pp.second << "\n";
    }

    for(auto &p: queries) {
        if(p.first==1) {
            edgelist[p.second.first].w = p.second.second; // just update first
        }
    }
    for(auto &p: queries) {
        if(p.first==1) {
            edgeset.insert(p.second.first);
        }
    }
    queries.clear();
    //isolate the queries of type 2

}
int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m; cin>>n>>m;
    //edge e;
    for(int i=0; i<m; i++) {
        int _u,_v,_w; cin>>_u>>_v>>_w;
        edge e = edge(_u,_v,_w);
        edgelist.push_back(e);
        edgeset.insert(i);
    }

    int q; cin>>q;
    while(q--) {
        pair<int, pair<int,int>> p;
        cin >> p.first >> p.second.first >> p.second.second;
        if(p.first==1) {
            p.second.first--;
        } else {
            swap(p.second.first, p.second.second);
        }
        queries.push_back(p);
        if(queries.size()==800) {
            clear_queries(n);
        }
    }
    clear_queries(n);
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void clear_queries(int)':
bridges.cpp:109:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<queries.size(); i++) {
                  ~^~~~~~~~~~~~~~~

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