oj.uz

Submission #261062

# Submission time Handle Problem Language Result Execution time Memory
261062 2020-08-11T10:50:11 Z dvdg6566 Colors (RMI18_colors) C++14
100 / 100
 1314 ms 129272 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MOD = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 160000;
const ll BSIZ= 800;

struct DSU{
	int p[MAXN];
	int sz[MAXN];
	stack<pi> stk;
	int N;
	int par(int x){return (p[x]==x)?x:par(p[x]);}
	DSU(){
		for(int i=1;i<MAXN;++i){
			p[i]=i;
			sz[i]=1;
		}
	}
	void merge(int a,int b){
		// cerr<<"Merge "<<a<<' '<<b<<'\n';
		a=par(a);b=par(b);
		if(a==b){
			stk.push(mp(-1,-1));
			return;
		}
		if(sz[a]<sz[b])swap(a,b);
		p[b]=a;
		sz[a]=sz[a]+sz[b];
		stk.push(mp(b, sz[b]));// merging b into a
	}
	void reverse(){
		// cerr<<"Split "<<edges.back().f<<' '<<edges.back().s<<'\n';
		pi x=stk.top();stk.pop();
		if(x.f==-1)return;
		int b=x.f;
		int a=p[b];
		int bsiz=x.s;
		p[b]=b;
		sz[a]-=bsiz;
	}
}*ufds;

int T,N,E,a,b;
int A[MAXN];
int B[MAXN];
int ans;
vi starts[MAXN];
vi ee[MAXN];
int easy[MAXN];

struct node{
	int s,e,m;
	node *l,*r;
	vpi V;
	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 addedge(int x,int y,pi z){
		if(s==x&&e==y){
			V.pb(z);return;
		}
		if(y<=m)l->addedge(x,y,z);
		else if(x>m)r->addedge(x,y,z);
		else{
			l->addedge(x,m,z);
			r->addedge(m+1,y,z);
		}
	}
	void solve(int N){
		for(auto i:V){
			ufds->merge(i.f,i.s);
		}
		if(s!=e){
			l->solve(N);
			if(m<N)r->solve(N);
		}else{
			if(SZ(ee[s])){
				for(auto i:starts[s])easy[ufds->par(i)]=1;
				for(auto i:ee[s])if(!easy[ufds->par(i)])ans=0;
				for(auto i:starts[s])easy[ufds->par(i)]=0;
			}
		}
		for(auto i:V)ufds->reverse();
		V.clear();
	}
}*root;

vpi egdeList;

int main(){
	cin>>T;
	ufds=new DSU();
	root=new node(1,MAXN);

	while(T--){
		cin>>N>>E;
		ans=1;
		for(int i=1;i<=N;++i){starts[i].clear();ee[i].clear();}
		for(int i=1;i<=N;++i)cin>>A[i];
		for(int i=1;i<=N;++i){
			cin>>B[i];
			ee[B[i]].pb(i);
			starts[A[i]].pb(i);
			if(B[i]>A[i])ans=0;
		}
		egdeList.clear();
		for(int i=0;i<E;++i){cin>>a>>b;egdeList.pb(a,b);}
		if(!ans){cout<<"0\n";continue;}
		for(auto i:egdeList){
			a=i.f;b=i.s;
			int latestart=max(B[a],B[b]);
			int firstend=min(A[a],A[b]);
			// cerr<<"Edge "<<a<<' '<<b<<" from  "<<latestart<<' '<<firstend<<'\n';
			if(latestart>firstend)continue;
			root->addedge(latestart,firstend,mp(a,b));
		}
		root->solve(N);
		cout<<ans<<'\n';
	}
}

Compilation message

colors.cpp: In member function 'void node::solve(int)':
colors.cpp:97:12: warning: variable 'i' set but not used [-Wunused-but-set-variable]
   for(auto i:V)ufds->reverse();
            ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 29816 KB Output is correct
2 Correct 94 ms 29944 KB Output is correct
3 Correct 36 ms 29824 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 30840 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 29688 KB Output is correct
2 Correct 89 ms 29816 KB Output is correct
3 Correct 36 ms 29568 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 29688 KB Output is correct
2 Correct 89 ms 29816 KB Output is correct
3 Correct 36 ms 29568 KB Output is correct
4 Correct 439 ms 32340 KB Output is correct
5 Correct 916 ms 64748 KB Output is correct
6 Correct 1314 ms 97868 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 29816 KB Output is correct
2 Correct 94 ms 29944 KB Output is correct
3 Correct 36 ms 29824 KB Output is correct
4 Correct 211 ms 29688 KB Output is correct
5 Correct 89 ms 29816 KB Output is correct
6 Correct 36 ms 29568 KB Output is correct
7 Correct 217 ms 30668 KB Output is correct
8 Correct 91 ms 29820 KB Output is correct
9 Correct 37 ms 29688 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 30088 KB Output is correct
2 Correct 863 ms 64840 KB Output is correct
3 Correct 917 ms 74828 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 29816 KB Output is correct
2 Correct 66 ms 30460 KB Output is correct
3 Correct 49 ms 29560 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 29816 KB Output is correct
2 Correct 94 ms 29944 KB Output is correct
3 Correct 36 ms 29824 KB Output is correct
4 Correct 226 ms 30840 KB Output is correct
5 Correct 211 ms 29688 KB Output is correct
6 Correct 89 ms 29816 KB Output is correct
7 Correct 36 ms 29568 KB Output is correct
8 Correct 439 ms 32340 KB Output is correct
9 Correct 916 ms 64748 KB Output is correct
10 Correct 1314 ms 97868 KB Output is correct
11 Correct 217 ms 30668 KB Output is correct
12 Correct 91 ms 29820 KB Output is correct
13 Correct 37 ms 29688 KB Output is correct
14 Correct 430 ms 30088 KB Output is correct
15 Correct 863 ms 64840 KB Output is correct
16 Correct 917 ms 74828 KB Output is correct
17 Correct 121 ms 29816 KB Output is correct
18 Correct 66 ms 30460 KB Output is correct
19 Correct 49 ms 29560 KB Output is correct
20 Correct 301 ms 32304 KB Output is correct
21 Correct 862 ms 69604 KB Output is correct
22 Correct 1259 ms 129272 KB Output is correct