oj.uz

Submission #403240

# Submission time Handle Problem Language Result Execution time Memory
403240 2021-05-13T00:07:13 Z jamezzz Colors (RMI18_colors) C++14
78 / 100
 3000 ms 98944 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(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:49: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]
   49 |   while(left<st.size()){
      |         ~~~~^~~~~~~~~~
colors.cpp: In function 'int main()':
colors.cpp:106:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |  int t;sf("%d",&t);
      |          ^
colors.cpp:108:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |   sf("%d%d",&n,&m);
      |     ^
colors.cpp:112:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   for(int i=1;i<=n;++i)sf("%d",&a[i]);
      |                          ^
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",&b[i]);
      |                          ^
colors.cpp:114:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |   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 29504 KB Output is correct
2 Correct 44 ms 15428 KB Output is correct
3 Correct 9 ms 8356 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 15116 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 30108 KB Output is correct
2 Correct 46 ms 15536 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 120 ms 30108 KB Output is correct
2 Correct 46 ms 15536 KB Output is correct
3 Correct 9 ms 8268 KB Output is correct
4 Correct 240 ms 54948 KB Output is correct
5 Correct 505 ms 78300 KB Output is correct
6 Correct 829 ms 98944 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 29504 KB Output is correct
2 Correct 44 ms 15428 KB Output is correct
3 Correct 9 ms 8356 KB Output is correct
4 Correct 120 ms 30108 KB Output is correct
5 Correct 46 ms 15536 KB Output is correct
6 Correct 9 ms 8268 KB Output is correct
7 Correct 143 ms 29904 KB Output is correct
8 Correct 44 ms 15360 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 223 ms 53976 KB Output is correct
2 Correct 457 ms 78108 KB Output is correct
3 Correct 476 ms 74356 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 11864 KB Output is correct
2 Correct 24 ms 9172 KB Output is correct
3 Correct 16 ms 8408 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 29504 KB Output is correct
2 Correct 44 ms 15428 KB Output is correct
3 Correct 9 ms 8356 KB Output is correct
4 Correct 103 ms 15116 KB Output is correct
5 Correct 120 ms 30108 KB Output is correct
6 Correct 46 ms 15536 KB Output is correct
7 Correct 9 ms 8268 KB Output is correct
8 Correct 240 ms 54948 KB Output is correct
9 Correct 505 ms 78300 KB Output is correct
10 Correct 829 ms 98944 KB Output is correct
11 Correct 143 ms 29904 KB Output is correct
12 Correct 44 ms 15360 KB Output is correct
13 Correct 10 ms 8396 KB Output is correct
14 Correct 223 ms 53976 KB Output is correct
15 Correct 457 ms 78108 KB Output is correct
16 Correct 476 ms 74356 KB Output is correct
17 Correct 55 ms 11864 KB Output is correct
18 Correct 24 ms 9172 KB Output is correct
19 Correct 16 ms 8408 KB Output is correct
20 Correct 154 ms 19920 KB Output is correct
21 Execution timed out 3065 ms 20200 KB Time limit exceeded
22 Halted 0 ms 0 KB -