Submission #857523

#	Time	Username	Problem	Language	Result	Execution time	Memory
857523		Abito	Collapse (JOI18_collapse)	C++17	5 / 100	15099 ms	5972 KiB

collapse

#include "collapse.h"
#include <bits/stdc++.h>
#define ep insert
#define F first
#define S second
using namespace std;
const int N=5005;
int n,q,m,par[N],sz[N],c;
int getpar(int x){
    if (par[x]==x) return x;
    return par[x]=getpar(par[x]);
}
bool link(int x,int y){
    x=getpar(x);y=getpar(y);
    if (x==y) return 0;
    if (sz[x]>sz[y]) swap(x,y);
    sz[y]+=sz[x];
    par[x]=y;
    return 1;
}
std::vector<int> simulateCollapse(
	int NN,
	std::vector<int> t,
	std::vector<int> x,
	std::vector<int> y,
	std::vector<int> w,
	std::vector<int> p
) {
    n=NN;c=x.size();q=w.size();
    vector<int> ans(q);
    for (int i=0;i<c;i++) if (x[i]>y[i]) swap(x[i],y[i]);
    for (int k=0;k<q;k++){
        for (int i=0;i<n;i++) par[i]=i,sz[i]=1;
        int comp=n;
        set<pair<int,int>> s;
        for (int i=0;i<=w[k];i++){
            if (x[i]<=p[k] && y[i]>p[k]) continue;
            if (y[i]<=p[k] && x[i]>p[k]) continue;
            if (t[i]) s.erase({x[i],y[i]});
            else s.ep({x[i],y[i]});
        }
        for (auto u:s) comp-=link(u.F,u.S);
        ans[k]=comp;
    }return ans;
}

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