Submission #411470

#	Time	Username	Problem	Language	Result	Execution time	Memory
411470		mhy908	Collapse (JOI18_collapse)	C++14	100 / 100	13610 ms	151428 KiB

collapse

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef pair<int, int> pii;

const int BUC=500;

struct UNION_FIND{
    int par[100010], sz[100010], cnt;
    vector<int> vc;
    void init(int num){for(int i=1; i<=num; i++)par[i]=i, sz[i]=1; cnt=0;}
    int findpar(int num){return num==par[num]?num:findpar(par[num]);}
    void mergepar(int a, int b){
        a=findpar(a);
        b=findpar(b);
        if(a==b)return;
        if(sz[a]<sz[b])swap(a, b);
        vc.eb(b);
        par[b]=a;
        sz[a]+=sz[b];
        cnt++;
    }
    void rollback(){
        int tmp=vc.back();
        vc.pop_back();
        sz[par[tmp]]-=sz[tmp];
        par[tmp]=tmp;
        cnt--;
    }
}uf;

int n, m, q, query[100010], ans[100010];
pair<int, pii> edge[100010];
vector<int> qlst[100010];

bool cmpl(pii a, pii b){return a.S<b.S;}
bool cmpr(pii a, pii b){return a.F>b.F;}

void solve(int s, int e){

    set<pii> edgs;
    for(int i=1; i<s; i++){
        if(edge[i].F==0)edgs.insert(edge[i].S);
        else edgs.erase(edge[i].S);
    }
    vector<pii> org;
    for(int i=s; i<=e; i++){
        if(edge[i].F&&edgs.find(edge[i].S)!=edgs.end()){
            edgs.erase(edge[i].S);
            org.eb(edge[i].S);
        }
    }

    vector<pair<int, pii> > nq;
    for(int i=s; i<=e; i++){
        for(auto j:qlst[i])nq.eb(query[j], mp(i, j));
    }

    vector<pii> nedge;
    for(auto i:edgs)nedge.eb(i);

    sort(all(nedge), cmpl);
    sort(all(nq));
    uf.init(n);

    int pv=0;
    for(auto i:nq){
        for(; pv<nedge.size(); pv++){
            if(nedge[pv].S>i.F)break;
            uf.mergepar(nedge[pv].F, nedge[pv].S);
        }
        set<pii> nadd;
        for(auto j:org)nadd.insert(j);
        for(int j=s; j<=i.S.F; j++){
            if(edge[j].F==0)nadd.insert(edge[j].S);
            else nadd.erase(edge[j].S);
        }

        int nsz=uf.vc.size();

        for(auto j:nadd){
            if(j.S<=i.F)uf.mergepar(j.F, j.S);
        }

        ans[i.S.S]+=i.F-uf.cnt;

        while(uf.vc.size()>nsz)uf.rollback();

    }

    sort(all(nedge), cmpr);
    reverse(all(nq));
    uf.init(n);
    pv=0;
    
    for(auto i:nq){
        for(; pv<nedge.size(); pv++){
            if(nedge[pv].F<=i.F)break;
            uf.mergepar(nedge[pv].F, nedge[pv].S);
        }
        set<pii> nadd;
        for(auto j:org)nadd.insert(j);
        for(int j=s; j<=i.S.F; j++){
            if(edge[j].F==0)nadd.insert(edge[j].S);
            else nadd.erase(edge[j].S);
        }

        int nsz=uf.vc.size();

        for(auto j:nadd){
            if(j.F>i.F)uf.mergepar(j.F, j.S);
        }

        ans[i.S.S]+=n-i.F-uf.cnt;

        while(uf.vc.size()>nsz)uf.rollback();

    }

}

/*
int main(){
    scanf("%d %d %d", &n, &m, &q);
    for(int i=1; i<=m; i++){
        scanf("%d %d %d", &edge[i].F, &edge[i].S.F, &edge[i].S.S);
        if(edge[i].S.F>edge[i].S.S)swap(edge[i].S.F, edge[i].S.S);
        edge[i].S.F++, edge[i].S.S++;
    }
    for(int i=1; i<=q; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        qlst[a+1].eb(i);
        query[i]=b+1;
    }

    for(int i=1; i<=m; i+=BUC)solve(i, min(m, i+BUC-1));
    for(int i=1; i<=q; i++)printf("%d\n", ans[i]);
}
*/

vector<int> simulateCollapse(
	int N,
	vector<int> T,
	vector<int> X,
	vector<int> Y,
	vector<int> W,
	vector<int> P
) {
    n=N; m=T.size(); q=W.size();
    for(int i=1; i<=m; i++){
        edge[i].F=T[i-1];
        edge[i].S.F=X[i-1];
        edge[i].S.S=Y[i-1];
        if(edge[i].S.F>edge[i].S.S)swap(edge[i].S.F, edge[i].S.S);
        edge[i].S.F++, edge[i].S.S++;
    }
    
    for(int i=1; i<=q; i++){
        int a=W[i-1], b=P[i-1];
        qlst[a+1].eb(i);
        query[i]=b+1;
    }
    
    vector<int> ret;
    
    for(int i=1; i<=m; i+=BUC)solve(i, min(m, i+BUC-1));
    for(int i=1; i<=q; i++)ret.eb(ans[i]);
    
    return ret;
}

Compilation message (stderr)

collapse.cpp: In function 'void solve(int, int)':
collapse.cpp:75:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(; pv<nedge.size(); pv++){
      |               ~~^~~~~~~~~~~~~
collapse.cpp:94:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |         while(uf.vc.size()>nsz)uf.rollback();
      |               ~~~~~~~~~~~~^~~~
collapse.cpp:104:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for(; pv<nedge.size(); pv++){
      |               ~~^~~~~~~~~~~~~
collapse.cpp:123:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  123 |         while(uf.vc.size()>nsz)uf.rollback();
      |               ~~~~~~~~~~~~^~~~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35