Submission #728596

#	Time	Username	Problem	Language	Result	Execution time	Memory
728596		Username4132	Bridges (APIO19_bridges)	C++14	100 / 100	1714 ms	12260 KiB

bridges

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second

struct query{
    int ind, ve, weight;
    query(int Ind, int Ve, int Weight) : ind(Ind), ve(Ve), weight(Weight){}
    query(){}
};

struct reversibleChange{
    int ind, sind, par, sz;
    reversibleChange(int Ind, int Sind, int Par, int Sz) : ind(Ind), sind(Sind), par(Par), sz(Sz){};
};

const int MAXN=50010, MAXE=100010;
int n, m, q, lastLeft[MAXE], lastFull[MAXE], lastSeen[MAXE], lastWeight[MAXE], par[MAXN], size[MAXN];
bool seen[MAXE], notodo[MAXE];
pii edges[MAXE];
vector<query> upd, ask, done;
vector<pii> ans;
vector<reversibleChange> changes;

auto cmp = [](query a, query b){
    return a.weight>b.weight;
};


int root(int a){
    while(par[a]!=a) a=par[a];
    return a;
}

void combine(int edgeInd, bool save){
    int a=edges[edgeInd].F, b=edges[edgeInd].S;
    int root_a=root(a), root_b=root(b);
    if(root_a==root_b) return;
    if(size[root_a]<size[root_b]) swap(root_a, root_b);

    if(!save) changes.PB(reversibleChange(root_a, root_b, par[root_b], size[root_a]));
    size[root_a]+=size[root_b];
    par[root_b]=root_a;
}

void rollback(){
    while(!changes.empty()){
        reversibleChange ch = changes.back();
        changes.pop_back();
        par[ch.sind]=ch.par;
        size[ch.ind]=ch.sz;
    }
}

void reset(){
    changes.clear();
    forn(i, n) par[i]=i, size[i]=1;
}


int main(){
    forn(i, MAXE) lastSeen[i]=-2;
    done.reserve(MAXE);
    scanf("%d %d", &n , &m);
    forn(i, m){
        int a, b, c; scanf("%d %d %d", &a, &b, &c); --a, --b;
        edges[i]={a, b};
        done.PB(query(i, i, c));
        lastWeight[i]=c;
    }
    upd.PB(query(-1, 0, lastWeight[0]));
    sort(done.begin(), done.end(), cmp);
    scanf("%d", &q);
    forn(i, q){
        int a, b, c; scanf("%d %d %d", &a, &b, &c);
        if(a==1) upd.PB(query(i+m, b-1, c));
        else ask.PB(query(i+m, b-1, c));
    }
    int qnum=upd.size(), sq=0, answered=0;

    while((sq+1)*(sq+1)<=qnum) ++sq;
    for(int l=0; l<qnum && answered<(int)ask.size(); l+=sq){
        reset();
        int r=min(l+sq, qnum);
        int bnd=(r==qnum? 1000000 : upd[r].ind);
        int lstQ=answered, updated=0;
        forsn(i, l, r) seen[upd[i].ve]=true;
        
        while(lstQ<(int)ask.size() && ask[lstQ].ind<bnd) ++lstQ;
        sort(ask.begin()+answered, ask.begin()+lstQ, cmp);
        forsn(i, answered, lstQ){
            query question = ask[i];
            while(updated<(int)done.size() && done[updated].weight>=question.weight){
                if(!seen[done[updated].ve]) combine(done[updated].ve, true);
                updated++;
            }
            forsn(j, l, r){
                if(upd[j].ind>question.ind) break;
                lastSeen[upd[j].ve]=j;
                notodo[upd[j].ve]=true;
            }
            forsn(j, l, r){
                if(lastSeen[upd[j].ve]==j && upd[j].weight>=question.weight) combine(upd[j].ve, false);
                else if(!notodo[upd[j].ve] && (lastWeight[upd[j].ve]>=question.weight)) combine(upd[j].ve, false);
            }
            int ret = size[root(question.ve)];
            ans.PB({question.ind, ret});
            forsn(j, l, r) notodo[upd[j].ve]=false, lastSeen[upd[j].ve]=-2;
            rollback();
        }
        answered=lstQ;
        vector<query> le, ri;
        forsn(i, l, r) lastSeen[upd[i].ve]=i;
        forn(i, done.size()) if(!seen[done[i].ve]) le.PB(done[i]);
        forsn(i, l, r) if(lastSeen[upd[i].ve]==i) ri.PB(upd[i]), lastWeight[upd[i].ve]=upd[i].weight;
        sort(ri.begin(), ri.end(), cmp);
        done.resize(le.size()+ri.size());
        merge(le.begin(), le.end(), ri.begin(), ri.end(), done.begin(), cmp);
        forsn(i, l, r) seen[upd[i].ve]=false;
    }

    sort(ans.begin(), ans.end());
    for(auto pr:ans) printf("%d\n", pr.S);
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     scanf("%d %d", &n , &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
bridges.cpp:72:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         int a, b, c; scanf("%d %d %d", &a, &b, &c); --a, --b;
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
bridges.cpp:81:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         int a, b, c; scanf("%d %d %d", &a, &b, &c);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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