oj.uz

Submission #403245

# Submission time Handle Problem Language Result Execution time Memory
403245 2021-05-13T00:16:39 Z jamezzz Colors (RMI18_colors) C++14
100 / 100
 847 ms 98916 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 29508 KB Output is correct
2 Correct 43 ms 15392 KB Output is correct
3 Correct 9 ms 8268 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 15084 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 30104 KB Output is correct
2 Correct 49 ms 15576 KB Output is correct
3 Correct 9 ms 8268 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 30104 KB Output is correct
2 Correct 49 ms 15576 KB Output is correct
3 Correct 9 ms 8268 KB Output is correct
4 Correct 258 ms 55000 KB Output is correct
5 Correct 492 ms 78208 KB Output is correct
6 Correct 847 ms 98916 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 29508 KB Output is correct
2 Correct 43 ms 15392 KB Output is correct
3 Correct 9 ms 8268 KB Output is correct
4 Correct 128 ms 30104 KB Output is correct
5 Correct 49 ms 15576 KB Output is correct
6 Correct 9 ms 8268 KB Output is correct
7 Correct 115 ms 29880 KB Output is correct
8 Correct 44 ms 15452 KB Output is correct
9 Correct 11 ms 8492 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 54056 KB Output is correct
2 Correct 460 ms 78084 KB Output is correct
3 Correct 474 ms 74528 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 11840 KB Output is correct
2 Correct 20 ms 9060 KB Output is correct
3 Correct 12 ms 8396 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 29508 KB Output is correct
2 Correct 43 ms 15392 KB Output is correct
3 Correct 9 ms 8268 KB Output is correct
4 Correct 92 ms 15084 KB Output is correct
5 Correct 128 ms 30104 KB Output is correct
6 Correct 49 ms 15576 KB Output is correct
7 Correct 9 ms 8268 KB Output is correct
8 Correct 258 ms 55000 KB Output is correct
9 Correct 492 ms 78208 KB Output is correct
10 Correct 847 ms 98916 KB Output is correct
11 Correct 115 ms 29880 KB Output is correct
12 Correct 44 ms 15452 KB Output is correct
13 Correct 11 ms 8492 KB Output is correct
14 Correct 232 ms 54056 KB Output is correct
15 Correct 460 ms 78084 KB Output is correct
16 Correct 474 ms 74528 KB Output is correct
17 Correct 47 ms 11840 KB Output is correct
18 Correct 20 ms 9060 KB Output is correct
19 Correct 12 ms 8396 KB Output is correct
20 Correct 129 ms 19816 KB Output is correct
21 Correct 458 ms 68588 KB Output is correct
22 Correct 687 ms 97216 KB Output is correct