Submission #403245

#	Time	Username	Problem	Language	Result	Execution time	Memory
403245		jamezzz	Colors (RMI18_colors)	C++14	100 / 100	847 ms	98916 KiB

colors

#include <bits/stdc++.h>
using namespace std;

//#define DEBUG

#ifdef DEBUG
#define debug(...) printf(__VA_ARGS__);
#else
#define debug(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;

int n,m,a[150005],b[150005],u[200005],v[200005];
bool pos;
vector<int> qry[150005],have[150005];

struct union_find{
	int par[150005],sz[150005];
	stack<ii> st;
	int fp(int i){
		return (par[i]==i)?i:fp(par[i]);
	}
	void join(int x,int y){
		x=fp(x),y=fp(y);
		if(x==y)return;
		if(sz[x]<sz[y])swap(x,y);
		par[y]=x;sz[x]+=sz[y];
		st.push(ii(x,y));
	}
	void rollback(int left){
		while(left<st.size()){
			int x,y;tie(x,y)=st.top();st.pop();
			par[y]=y;sz[x]-=sz[y];
		}
	}
}ufds;

struct node{
	int s,e,m;vii v;
	node *l,*r;
	
	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 add(int x,int y,ii nv){
		if(s==x&&e==y){
			v.pb(nv);return;
		}
		if(y<=m)l->add(x,y,nv);
		else if(x>m)r->add(x,y,nv);
		else l->add(x,m,nv),r->add(m+1,y,nv);
	}
	void descend(){
		if(!pos)return;
		int enter_size=ufds.st.size();
		for(ii p:v){
			debug("join: %d %d\n",p.fi,p.se);
			ufds.join(p.fi,p.se);
		}
		if(s==e){
			debug("query: %d\n",s);
			set<int> src;
			for(int x:have[s]){
				debug("add: %d\n",ufds.fp(x));
				src.insert(ufds.fp(x));
			}
			for(int x:qry[s]){
				int par=ufds.fp(x);
				debug("ask: %d %d\n",par,src.find(par)==src.end());
				if(src.find(par)==src.end()){
					pos=false;break;
				}
			}
		}
		else{
			l->descend();
			r->descend();
		}
		ufds.rollback(enter_size);
	}
}*root;

int main(){
	int t;sf("%d",&t);
	while(t--){
		sf("%d%d",&n,&m);
		pos=true;
		root=new node(1,n);
		for(int i=1;i<=n;++i)qry[i].clear(),have[i].clear();
		for(int i=1;i<=n;++i)sf("%d",&a[i]);
		for(int i=1;i<=n;++i)sf("%d",&b[i]);
		for(int i=0;i<m;++i)sf("%d%d",&u[i],&v[i]);
		for(int i=1;i<=n;++i){
			if(b[i]>a[i]){
				pos=false;break;
			}
			ufds.sz[i]=1;
			ufds.par[i]=i;
			while(!ufds.st.empty())ufds.st.pop();
			qry[b[i]].pb(i);
			have[a[i]].pb(i);
		}
		if(!pos){
			printf("0\n");
			continue;
		}
		for(int i=0;i<m;++i){
			int lo=max(b[u[i]],b[v[i]]);
			int hi=min(a[u[i]],a[v[i]]);
			debug("edge: %d %d %d %d\n",u[i],v[i],lo,hi);
			if(lo>hi)continue;
			root->add(lo,hi,ii(u[i],v[i]));
		}
		root->descend();
		pf("%d\n",pos);
	}
}

/*
2
4 4
3 3 2 1
2 1 2 1
1 2
2 3
3 4
4 2
4 4
3 3 2 1
1 2 2 1
1 2
2 3
3 4
4 2
*/

Compilation message (stderr)

colors.cpp: In member function 'void union_find::rollback(int)':
colors.cpp:50:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   while(left<st.size()){
      |         ~~~~^~~~~~~~~~
colors.cpp: In function 'int main()':
colors.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |  int t;sf("%d",&t);
      |          ^
colors.cpp:109:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |   sf("%d%d",&n,&m);
      |     ^
colors.cpp:113:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |   for(int i=1;i<=n;++i)sf("%d",&a[i]);
      |                          ^
colors.cpp:114:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |   for(int i=1;i<=n;++i)sf("%d",&b[i]);
      |                          ^
colors.cpp:115:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |   for(int i=0;i<m;++i)sf("%d%d",&u[i],&v[i]);
      |                         ^

• 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