Submission #1349431

#TimeUsernameProblemLanguageResultExecution timeMemory
1349431khanhphucscratchBridges (APIO19_bridges)C++20
100 / 100
2080 ms132176 KiB
#include<bits/stdc++.h>
using namespace std;
stack<int> history;
int root[50005], sz[50005];
void init(int n)
{
    for(int i = 1; i <= n; i++){root[i] = i; sz[i] = 1;}
}
int getroot(int u)
{
    if(root[u] == u) return u;
    else return getroot(root[u]);
}
void unite(int u, int v)
{
    //cerr<<"A"<<u<<" "<<v<<" "<<sz[2]<<endl;
    u = getroot(u); v = getroot(v);
    if(u == v){history.push(-1); return;}
    if(sz[u] < sz[v]) swap(u, v);
    history.push(v); sz[u] += sz[v]; root[v] = u;
}
void rollback()
{
    if(history.size() == 0) return;
    int v = history.top(); history.pop();
    if(v == -1) return;
    //cerr<<"B "<<v<<" "<<root[v]<<endl;
    sz[root[v]] -= sz[v]; root[v] = v;
}
pair<pair<int, int>, int> edges[100005];
int ans[100005], real_val[100005]; //Just some array that don't need to be clean
const int bs = 320; /**/
bool modify[100005];
int main()
{
    int n, m; cin>>n>>m;
    for(int i = 1; i <= m; i++) cin>>edges[i].first.first>>edges[i].first.second>>edges[i].second;
    //Solve all queries
    int q; cin>>q;
    vector<vector<int>> w;
    memset(ans, -1, sizeof(ans));
    vector<int> edge_order;
    for(int i = 1; i <= m; i++) edge_order.push_back(i);
    for(int it = 1; it <= q; it++){
        vector<int> cur_question(3);
        for(int &j : cur_question) cin>>j;
        w.push_back(cur_question);
        if(w.size() == bs | it == q){
            init(n);
            //Solve
            memset(modify, 0, sizeof(modify));
            vector<int> question_idx, small_edge;
            for(int i = 0; i < w.size(); i++){
                if(w[i][0] == 1){modify[w[i][1]] = 1; small_edge.push_back(w[i][1]);}
                else question_idx.push_back(i);
            }
            sort(small_edge.begin(), small_edge.end()); small_edge.erase(unique(small_edge.begin(), small_edge.end()), small_edge.end());
            memset(real_val, -1, sizeof(real_val));
            //Sort edges and queries
            sort(edge_order.begin(), edge_order.end(), [&](int x, int y){return edges[x].second > edges[y].second;});
            sort(question_idx.begin(), question_idx.end(), [&](int x, int y){return w[x][2] > w[y][2];});
            int j = 0;
            for(int idx : question_idx){
                //Load the other edges
                //cerr<<"B"<<it<<" "<<j<<" "<<edges[edge_order[j]].second<<endl;
                while(j < edge_order.size() && edges[edge_order[j]].second >= w[idx][2]){
                    int u = edges[edge_order[j]].first.first, v = edges[edge_order[j]].first.second;
                    //if(it == 2) cerr<<"A"<<u<<" "<<v<<endl;
                    if(modify[edge_order[j]] == 0) unite(u, v);
                    j++;
                }
                //Deal with the edges in the current set
                for(int i = 0; i < idx; i++) if(w[i][0] == 1) real_val[w[i][1]] = w[i][2];
                int num = 0;
                for(int i : small_edge){
                    int c = real_val[i];
                    if(c == -1) c = edges[i].second;
                    if(c >= w[idx][2]){
                        unite(edges[i].first.first, edges[i].first.second);
                        //if(it == 2) cerr<<"A"<<edges[i].first.first<<" "<<edges[i].first.second<<endl;
                        num++;
                    }
                }
                //Answer the query
                int real_idx = it+1-(w.size() - idx);
                int u = w[idx][1]; u = getroot(u);
                //cerr<<"C"<<real_idx<<" "<<u<<endl;
                ans[real_idx] = sz[u];
                //Rollback
                for(int i = 0; i < idx; i++) if(w[i][0] == 1) real_val[w[i][1]] = -1;
                while(num--) rollback();
            }
            //Update all edges after
            for(int i = 0; i < w.size(); i++) if(w[i][0] == 1) edges[w[i][1]].second = w[i][2];
            w.clear();
        }
    }
    for(int i = 1; i <= q; i++) if(ans[i] != -1) cout<<ans[i]<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...