oj.uz

Submission #403241

# Submission time Handle Problem Language Result Execution time Memory
403241 2021-05-13T00:08:10 Z jamezzz Colors (RMI18_colors) C++14
78 / 100
 896 ms 98964 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;
			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 111 ms 29484 KB Output is correct
2 Correct 49 ms 15356 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 93 ms 15188 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 30060 KB Output is correct
2 Correct 45 ms 15544 KB Output is correct
3 Correct 11 ms 8268 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 30060 KB Output is correct
2 Correct 45 ms 15544 KB Output is correct
3 Correct 11 ms 8268 KB Output is correct
4 Correct 261 ms 54936 KB Output is correct
5 Correct 526 ms 78196 KB Output is correct
6 Correct 896 ms 98964 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 29484 KB Output is correct
2 Correct 49 ms 15356 KB Output is correct
3 Correct 9 ms 8268 KB Output is correct
4 Correct 144 ms 30060 KB Output is correct
5 Correct 45 ms 15544 KB Output is correct
6 Correct 11 ms 8268 KB Output is correct
7 Correct 133 ms 29932 KB Output is correct
8 Correct 56 ms 15412 KB Output is correct
9 Correct 13 ms 8396 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 53956 KB Output is correct
2 Correct 495 ms 78232 KB Output is correct
3 Correct 553 ms 74392 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 11820 KB Output is correct
2 Correct 20 ms 9144 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 111 ms 29484 KB Output is correct
2 Correct 49 ms 15356 KB Output is correct
3 Correct 9 ms 8268 KB Output is correct
4 Correct 93 ms 15188 KB Output is correct
5 Correct 144 ms 30060 KB Output is correct
6 Correct 45 ms 15544 KB Output is correct
7 Correct 11 ms 8268 KB Output is correct
8 Correct 261 ms 54936 KB Output is correct
9 Correct 526 ms 78196 KB Output is correct
10 Correct 896 ms 98964 KB Output is correct
11 Correct 133 ms 29932 KB Output is correct
12 Correct 56 ms 15412 KB Output is correct
13 Correct 13 ms 8396 KB Output is correct
14 Correct 223 ms 53956 KB Output is correct
15 Correct 495 ms 78232 KB Output is correct
16 Correct 553 ms 74392 KB Output is correct
17 Correct 47 ms 11820 KB Output is correct
18 Correct 20 ms 9144 KB Output is correct
19 Correct 12 ms 8396 KB Output is correct
20 Correct 143 ms 19804 KB Output is correct
21 Correct 481 ms 73508 KB Output is correct
22 Incorrect 221 ms 61516 KB Output isn't correct