Submission #207104

#	Time	Username	Problem	Language	Result	Execution time	Memory
207104		Segtree	Collapse (JOI18_collapse)	C++14	5 / 100	15087 ms	6136 KiB

collapse

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<unordered_set>
#include"collapse.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(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
//namespace solver1{
	vi 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){
		int C=T.size(),Q=W.size();
		for(int i=0;i<C;i++){
			if(X[i]>Y[i])swap(X[i],Y[i]);
		}
		vi FANS(Q);
		for(int i=0;i<Q;i++){
			for(int j=0;j<N;j++){
				g[j].clear();
				vis[j]=0;
			}
			unordered_set<ll> S;
			for(int j=0;j<=W[i];j++){
				ll key=X[j]*5010+Y[j];
				if(S.count(key))S.erase(key);
				else S.insert(key);
			}
			for(auto key:S){
				ll x=key/5010,y=key%5010;
				if(not(x<=P[i]&&P[i]+1<=y)){
					g[x].push_back(y);
					g[y].push_back(x);
				}
			}
			
			ll cnt=0;
			for(int j=0;j<N;j++){
				if(vis[j])continue;
				dfs(j);
				cnt++;
			}
			FANS[i]=cnt;
		}
		return FANS;
	}
//};
/*int main(){
	ll N,C,Q;
	cin>>N>>C>>Q;
	vi T(C),X(C),Y(C),W(Q),P(Q);
	rep(i,C){
		cin>>T[i]>>X[i]>>Y[i];
	}
	rep(i,Q){
		cin>>W[i]>>P[i];
	}
	vi ANS1=solver1::simulateCollapse(N,T,X,Y,W,P);
	for(auto t:ANS1)cout<<t<<endl;
}*/

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