oj.uz

Submission #403243

# Submission time Handle Problem Language Result Execution time Memory
403243 2021-05-13T00:11:21 Z jamezzz Colors (RMI18_colors) C++14
78 / 100
 839 ms 98980 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[150005],v[150005];
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;
			}
			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 118 ms 29512 KB Output is correct
2 Correct 43 ms 15320 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 90 ms 15160 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 30156 KB Output is correct
2 Correct 44 ms 15476 KB Output is correct
3 Correct 10 ms 8224 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 30156 KB Output is correct
2 Correct 44 ms 15476 KB Output is correct
3 Correct 10 ms 8224 KB Output is correct
4 Correct 239 ms 54896 KB Output is correct
5 Correct 507 ms 78196 KB Output is correct
6 Correct 839 ms 98980 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 29512 KB Output is correct
2 Correct 43 ms 15320 KB Output is correct
3 Correct 9 ms 8268 KB Output is correct
4 Correct 119 ms 30156 KB Output is correct
5 Correct 44 ms 15476 KB Output is correct
6 Correct 10 ms 8224 KB Output is correct
7 Correct 117 ms 29952 KB Output is correct
8 Correct 45 ms 15376 KB Output is correct
9 Correct 10 ms 8396 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 54044 KB Output is correct
2 Correct 469 ms 78148 KB Output is correct
3 Correct 493 ms 74484 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 11852 KB Output is correct
2 Correct 21 ms 9036 KB Output is correct
3 Correct 12 ms 8396 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 29512 KB Output is correct
2 Correct 43 ms 15320 KB Output is correct
3 Correct 9 ms 8268 KB Output is correct
4 Correct 90 ms 15160 KB Output is correct
5 Correct 119 ms 30156 KB Output is correct
6 Correct 44 ms 15476 KB Output is correct
7 Correct 10 ms 8224 KB Output is correct
8 Correct 239 ms 54896 KB Output is correct
9 Correct 507 ms 78196 KB Output is correct
10 Correct 839 ms 98980 KB Output is correct
11 Correct 117 ms 29952 KB Output is correct
12 Correct 45 ms 15376 KB Output is correct
13 Correct 10 ms 8396 KB Output is correct
14 Correct 228 ms 54044 KB Output is correct
15 Correct 469 ms 78148 KB Output is correct
16 Correct 493 ms 74484 KB Output is correct
17 Correct 47 ms 11852 KB Output is correct
18 Correct 21 ms 9036 KB Output is correct
19 Correct 12 ms 8396 KB Output is correct
20 Correct 126 ms 19956 KB Output is correct
21 Correct 464 ms 68804 KB Output is correct
22 Incorrect 214 ms 54220 KB Output isn't correct