Submission #201989

#	Time	Username	Problem	Language	Result	Execution time	Memory
201989		Segtree	Collapse (JOI18_collapse)	C++14	0 / 100	75 ms	4432 KiB

collapse

#include<bits/stdc++.h>
#include"collapse.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
int n,m,q;
vector<ll> g[5010];
bool vis[5010];
void dfs(ll x){
    if(vis[x])return;
    vis[x]=1;
    for(auto y:g[x])dfs(y);
}
vi simulateCollapse(int N,vi t,vi x,vi y,vi w,vi p){
    n=N,m=t.size(),q=w.size();
    rep(i,m)if(x[i]>y[i])swap(x[i],y[i]);
    vi fans;
    rep(k,q){
	rep(i,n)g[i].clear();
	unordered_set<ll> S;
	for(int i=w[k];i>=0;i--){
	    if(S.find(x[i]*5010+y[i])==S.end()){
		if(t[k]==0&&not(x[i]<=p[k]&&p[k]+1<=y[i])){
		    g[x[i]].push_back(y[i]);
		    g[y[i]].push_back(x[i]);
		}
		S.insert(x[i]*5010+y[i]);
	    }
	}
	rep(i,n)vis[i]=0;
	ll ans=0;
	rep(i,n)if(!vis[i]){
	    ans++;
	    dfs(i);
	}
	fans.push_back(ans);
    }
    return fans;
}
/*int main(){
    
}*/

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