oj.uz

Submission #851813

# Submission time Handle Problem Language Result Execution time Memory
851813 2023-09-20T16:18:13 Z TimDee Colors (RMI18_colors) C++17
78 / 100
 441 ms 59076 KB 
//  Esti <3

//\
     šťastia pre nás :)
//   you're already the best
//             _
//   ^ ^      //
// >(O_O)<___//
//   \ __ __  \
//    \\ \\ \\\\
 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
//#define int long long
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second 
#define vii(a,n) vector<int> a(n); forn(i,n) cin>>a[i];
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int inf = 1e18;
const int mod = 998244353;
 
// \
\
:smiling_face_with_3_hearts: :smiling_face_with_3_hearts:  :smiling_face_with_3_hearts:  
 
//vidime sa veľmi skoro, moje slnko
	
const int N = 2e5+5;

int n,m;
int a[N], b[N];
pi e[N];
int is[N], r[N];
vector<pi> adj[N];

bitset<N> vis;
bitset<N> ok;
vector<int> g[N];
 
int dfs(int u, int x) {
	if (a[u] < x) return 0;
	if (a[u]==x) return 1;
	if (vis[u]) return 0;
	if (ok[u]) return 0;
	vis[u]=1;
	for(auto&v:g[u]) {
		dfs(v,x);
		if (a[v]==x) a[u]=x;
	}
	return a[u]==x;
}
 
int can(int s, int x) {
	vis.reset();
	return dfs(s,x);
}

void bad() {

	forn(i,n) g[i].clear();
	ok.reset();
	forn(i,m) {
		int u=e[i].f, v=e[i].s; --u, --v;
		g[u].pb(v);
		g[v].pb(u);
	}
 
	vector<pi> v;
	forn(i,n) v.pb({b[i],i});
	sort(rall(v));
 
	for(auto&x:v) {
		int z = can(x.s, x.f);
		if (!z) {
			cout<<"0\n"; return;
		}
		ok[x.s]=1;
	}
	cout<<"1\n";

}


struct DSU {
	vector<int> p,sz,mn;
	vector<pi> rb;
	void init(int n) {
		p.clear(); sz.clear(); mn.clear(); rb.clear();
		forn(i,n) p.pb(i), sz.pb(1), mn.pb(a[i]);
	}
	int get(int u) {
		return p[u]==u?u:get(p[u]);
	}
	void uni(int u, int v) {
		u=get(u), v=get(v);
		if (u==v) {
			rb.pb({-1,-1}); return;
		}
		if (sz[u]<sz[v]) swap(u,v);
		p[v]=u;
		sz[u]+=sz[v];
		rb.pb({v,mn[u]});
		mn[u]=min(mn[u],mn[v]);
	}
	void roll() {
		auto it = rb.back(); rb.pop_back();
		int v = it.f, old = it.s;
		int u = p[v];
		p[v] = v;
		sz[u] -= sz[v];
		mn[u] = old;
	}
};

DSU dsu;

struct sgt {
	vector<vector<int>> t; int sz=1;
	int l,r,v;
	void init(int n) {
		t.clear();
		sz=1;
		while (sz<n) sz<<=1;
		t.resize(2*sz);
		l=0, r=sz, v=0;
	}
	void add(int v, int l, int r, int lx, int rx, int i) {
		if (rx<=l || r<=lx) return;
		if (lx<=l && r<=rx) {
			t[v].pb(i); return;
		}
		int m=(l+r)>>1;
		add(2*v+1,l,m,lx,rx,i);
		add(2*v+2,m,r,lx,rx,i);
	}
	void add(int l, int r, int i) {
		add(0,0,sz,l,r,i);
	}
	void go(int i) {
		while (r<=i) {
			if (v&1) r+=r-l;
			else l-=r-l;
			for(auto&x:t[v]) dsu.roll();
			v = (v-1)>>1;
		}
		while (r-l > 1) {
			int m = (l+r)>>1;
			if (i<m) {
				r=m;
				v=2*v+1;
			} else {
				l=m;
				v=2*v+2;
			}
			for(auto&x:t[v]) dsu.uni(e[x].f, e[x].s);
		}
	}
};
sgt st;

void solve() {

	cin>>n>>m;
	forn(i,n) cin>>a[i];
	forn(i,n) cin>>b[i];
	forn(i,m) cin>>e[i].f>>e[i].s;

	forn(i,n) {
		if (a[i]<b[i]) {
			cout<<"0\n"; return;
		}
	}
	if (n<=5000) {
		bad(); return;
	}

	forn(i,n) adj[i].clear();
	forn(i,m) is[i]=r[i]=0;
	dsu.init(n+5);
	st.init(n+5);

	forn(i,m) {
		--e[i].f, --e[i].s;
		int u=e[i].f, v=e[i].s;
		adj[u].pb({v,i});
		adj[v].pb({u,i});
	}

	vector<vector<int>> A(n+1), B(n+1);
	forn(i,n) A[a[i]].pb(i);
	forn(i,n) B[b[i]].pb(i);

	for (int i=n; i>0; --i) {
		for(auto&u:A[i]) {
			for(auto&e:adj[u]) {
				int v = e.s, j = e.s;
				if (is[j]>=2) continue;
				is[j]++;
				if (is[j]==2) r[j] = i+1;
				//cout<<"! "<<j<<' '<<i+1<<'\n';
			}
		}
		for(auto&u:B[i]) {
			for(auto&e:adj[u]) {
				int v = e.s, j = e.s;
				if (is[j]<2) {
					is[j]=4; continue;
				}
				if (is[j]>2) continue;
				is[j]=3;
				st.add(i, r[j], j);
				//cout<<j<<": "<<::e[j].f<<' '<<::e[j].s<<"  "<<i<<' '<<r[j]<<'\n';
			}
		}
	}

	for (int i=1; i<=n; ++i) {
		st.go(i);
		//cout<<"! "<<i<<": ";
		//forn(j,n) cout<<dsu.get(j)<<' '; cout<<'\n';
		for(auto&u:B[i]) {
			int p = dsu.get(u);
			int m = dsu.mn[p];
			if (m != i) {
				cout<<"0\n"; return;
			}
		}
	}
	cout<<"1\n";

}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t=1;
    cin>>t;
    while (t--) solve();
    return 0;
}

Compilation message

colors.cpp:3:1: warning: multi-line comment [-Wcomment]
    3 | //\
      | ^
colors.cpp:9:1: warning: multi-line comment [-Wcomment]
    9 | //   \ __ __  \
      | ^
colors.cpp:30:1: warning: multi-line comment [-Wcomment]
   30 | // \
      | ^
colors.cpp:27:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   27 | const int inf = 1e18;
      |                 ^~~~
colors.cpp: In member function 'void sgt::go(int)':
colors.cpp:151:13: warning: unused variable 'x' [-Wunused-variable]
  151 |    for(auto&x:t[v]) dsu.roll();
      |             ^
colors.cpp: In function 'void solve()':
colors.cpp:204:9: warning: unused variable 'v' [-Wunused-variable]
  204 |     int v = e.s, j = e.s;
      |         ^
colors.cpp:213:9: warning: unused variable 'v' [-Wunused-variable]
  213 |     int v = e.s, j = e.s;
      |         ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 12888 KB Output is correct
2 Correct 23 ms 12888 KB Output is correct
3 Correct 4 ms 13088 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 12888 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 12892 KB Output is correct
2 Correct 22 ms 12888 KB Output is correct
3 Correct 5 ms 12888 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 12892 KB Output is correct
2 Correct 22 ms 12888 KB Output is correct
3 Correct 5 ms 12888 KB Output is correct
4 Correct 124 ms 12888 KB Output is correct
5 Correct 255 ms 27784 KB Output is correct
6 Correct 441 ms 59076 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 12888 KB Output is correct
2 Correct 23 ms 12888 KB Output is correct
3 Correct 4 ms 13088 KB Output is correct
4 Correct 71 ms 12892 KB Output is correct
5 Correct 22 ms 12888 KB Output is correct
6 Correct 5 ms 12888 KB Output is correct
7 Correct 64 ms 12936 KB Output is correct
8 Correct 23 ms 12892 KB Output is correct
9 Correct 5 ms 12892 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 12988 KB Output is correct
2 Correct 308 ms 30244 KB Output is correct
3 Correct 281 ms 55852 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 12888 KB Output is correct
2 Correct 9 ms 12888 KB Output is correct
3 Correct 5 ms 12888 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 12888 KB Output is correct
2 Correct 23 ms 12888 KB Output is correct
3 Correct 4 ms 13088 KB Output is correct
4 Correct 43 ms 12888 KB Output is correct
5 Correct 71 ms 12892 KB Output is correct
6 Correct 22 ms 12888 KB Output is correct
7 Correct 5 ms 12888 KB Output is correct
8 Correct 124 ms 12888 KB Output is correct
9 Correct 255 ms 27784 KB Output is correct
10 Correct 441 ms 59076 KB Output is correct
11 Correct 64 ms 12936 KB Output is correct
12 Correct 23 ms 12892 KB Output is correct
13 Correct 5 ms 12892 KB Output is correct
14 Correct 126 ms 12988 KB Output is correct
15 Correct 308 ms 30244 KB Output is correct
16 Correct 281 ms 55852 KB Output is correct
17 Correct 21 ms 12888 KB Output is correct
18 Correct 9 ms 12888 KB Output is correct
19 Correct 5 ms 12888 KB Output is correct
20 Correct 54 ms 12980 KB Output is correct
21 Runtime error 47 ms 37224 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -