Submission #261062

#	Time	Username	Problem	Language	Result	Execution time	Memory
261062		dvdg6566	Colors (RMI18_colors)	C++14	100 / 100	1314 ms	129272 KiB

colors

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MOD = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 160000;
const ll BSIZ= 800;

struct DSU{
	int p[MAXN];
	int sz[MAXN];
	stack<pi> stk;
	int N;
	int par(int x){return (p[x]==x)?x:par(p[x]);}
	DSU(){
		for(int i=1;i<MAXN;++i){
			p[i]=i;
			sz[i]=1;
		}
	}
	void merge(int a,int b){
		// cerr<<"Merge "<<a<<' '<<b<<'\n';
		a=par(a);b=par(b);
		if(a==b){
			stk.push(mp(-1,-1));
			return;
		}
		if(sz[a]<sz[b])swap(a,b);
		p[b]=a;
		sz[a]=sz[a]+sz[b];
		stk.push(mp(b, sz[b]));// merging b into a
	}
	void reverse(){
		// cerr<<"Split "<<edges.back().f<<' '<<edges.back().s<<'\n';
		pi x=stk.top();stk.pop();
		if(x.f==-1)return;
		int b=x.f;
		int a=p[b];
		int bsiz=x.s;
		p[b]=b;
		sz[a]-=bsiz;
	}
}*ufds;

int T,N,E,a,b;
int A[MAXN];
int B[MAXN];
int ans;
vi starts[MAXN];
vi ee[MAXN];
int easy[MAXN];

struct node{
	int s,e,m;
	node *l,*r;
	vpi V;
	node(int _s,int _e):s(_s),e(_e){
		m=(s+e)/2;
		if(s!=e){l=new node(s,m);r=new node(m+1,e);}
	}
	void addedge(int x,int y,pi z){
		if(s==x&&e==y){
			V.pb(z);return;
		}
		if(y<=m)l->addedge(x,y,z);
		else if(x>m)r->addedge(x,y,z);
		else{
			l->addedge(x,m,z);
			r->addedge(m+1,y,z);
		}
	}
	void solve(int N){
		for(auto i:V){
			ufds->merge(i.f,i.s);
		}
		if(s!=e){
			l->solve(N);
			if(m<N)r->solve(N);
		}else{
			if(SZ(ee[s])){
				for(auto i:starts[s])easy[ufds->par(i)]=1;
				for(auto i:ee[s])if(!easy[ufds->par(i)])ans=0;
				for(auto i:starts[s])easy[ufds->par(i)]=0;
			}
		}
		for(auto i:V)ufds->reverse();
		V.clear();
	}
}*root;

vpi egdeList;

int main(){
	cin>>T;
	ufds=new DSU();
	root=new node(1,MAXN);

	while(T--){
		cin>>N>>E;
		ans=1;
		for(int i=1;i<=N;++i){starts[i].clear();ee[i].clear();}
		for(int i=1;i<=N;++i)cin>>A[i];
		for(int i=1;i<=N;++i){
			cin>>B[i];
			ee[B[i]].pb(i);
			starts[A[i]].pb(i);
			if(B[i]>A[i])ans=0;
		}
		egdeList.clear();
		for(int i=0;i<E;++i){cin>>a>>b;egdeList.pb(a,b);}
		if(!ans){cout<<"0\n";continue;}
		for(auto i:egdeList){
			a=i.f;b=i.s;
			int latestart=max(B[a],B[b]);
			int firstend=min(A[a],A[b]);
			// cerr<<"Edge "<<a<<' '<<b<<" from  "<<latestart<<' '<<firstend<<'\n';
			if(latestart>firstend)continue;
			root->addedge(latestart,firstend,mp(a,b));
		}
		root->solve(N);
		cout<<ans<<'\n';
	}
}

Compilation message (stderr)

colors.cpp: In member function 'void node::solve(int)':
colors.cpp:97:12: warning: variable 'i' set but not used [-Wunused-but-set-variable]
   for(auto i:V)ufds->reverse();
            ^

• Subtask 1: 15 / 15
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 10 / 10
• Subtask 8: 22 / 22