Submission #261032

#	Time	Username	Problem	Language	Result	Execution time	Memory
261032		dvdg6566	Colors (RMI18_colors)	C++14	0 / 100	89 ms	29876 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;
	vpi edges;
	int N;
	int par(int x){return (p[x]==x)?x:par(p[x]);}
	DSU(){}
	void reset(int _N){
		N=_N;
		for(int i=1;i<=N;++i){p[i]=i;sz[i]=1;}
	}
	void merge(int a,int b){
		// cerr<<"Merge "<<a<<' '<<b<<'\n';
		a=par(a);b=par(b);
		edges.pb(a,b);
		if(a==b){
			stk.push(mp(-1,-1));
			return;
		}
		if(sz[a]<sz[b])swap(a,b);
		// merging b into a
		p[b]=a;
		sz[a]=sz[a]+sz[b];
		stk.push(mp(b, sz[b]));
	}
	void reverse(){
		// cerr<<"Split "<<edges.back().f<<' '<<edges.back().s<<'\n';
		edges.pop_back();
		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[b]=bsiz;
		sz[a]-=bsiz;
	}
	void db(){
		cerr<<"Edges\n";
		for(auto i:edges)cerr<<i.f<<' '<<i.s<<'\n';
	}
}*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){
		int k=SZ(ufds->edges);
		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])){
				// cerr<<"Time "<<s<<'\n';
				// for(auto i:starts[s])cerr<<ufds->par(i)<<' ';cerr<<'\n';
				// for(auto i:ee[s])cerr<<ufds->par(i)<<' ';cerr<<'\n';
				// ufds->db();

				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;
				// cerr<<"Ans "<<ans<<'\n';
			}
		}
		for(auto i:V)ufds->reverse();
		V.clear();
		assert(k==SZ(ufds->edges));
	}
}*root;

int main(){
	cin>>T;
	ufds=new DSU();

	while(T--){
		cin>>N>>E;
		root=new node(1,N);
		ufds->reset(N);
		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;
		}
		if(!ans){cout<<"0\n";continue;}
		while(E--){
			cin>>a>>b;
			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:112:12: warning: variable 'i' set but not used [-Wunused-but-set-variable]
   for(auto i:V)ufds->reverse();
            ^

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