oj.uz

Submission #851817

# Submission time Handle Problem Language Result Execution time Memory
851817 2023-09-20T16:22:11 Z TimDee Colors (RMI18_colors) C++17
100 / 100
 453 ms 63032 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];


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;
		if (v==-1) return;
		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;
		}
	}

	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:105:13: warning: unused variable 'x' [-Wunused-variable]
  105 |    for(auto&x:t[v]) dsu.roll();
      |             ^
colors.cpp: In function 'void solve()':
colors.cpp:155:9: warning: unused variable 'v' [-Wunused-variable]
  155 |     int v = e.s, j = e.s;
      |         ^
colors.cpp:164:9: warning: unused variable 'v' [-Wunused-variable]
  164 |     int v = e.s, j = e.s;
      |         ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 8792 KB Output is correct
2 Correct 28 ms 8992 KB Output is correct
3 Correct 4 ms 9048 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 8796 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 8876 KB Output is correct
2 Correct 33 ms 8792 KB Output is correct
3 Correct 4 ms 9052 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 8876 KB Output is correct
2 Correct 33 ms 8792 KB Output is correct
3 Correct 4 ms 9052 KB Output is correct
4 Correct 148 ms 9156 KB Output is correct
5 Correct 286 ms 23448 KB Output is correct
6 Correct 453 ms 54232 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 8792 KB Output is correct
2 Correct 28 ms 8992 KB Output is correct
3 Correct 4 ms 9048 KB Output is correct
4 Correct 77 ms 8876 KB Output is correct
5 Correct 33 ms 8792 KB Output is correct
6 Correct 4 ms 9052 KB Output is correct
7 Correct 71 ms 8900 KB Output is correct
8 Correct 27 ms 8796 KB Output is correct
9 Correct 5 ms 9052 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 8968 KB Output is correct
2 Correct 299 ms 25904 KB Output is correct
3 Correct 301 ms 51200 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 8804 KB Output is correct
2 Correct 11 ms 9304 KB Output is correct
3 Correct 7 ms 9052 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 8792 KB Output is correct
2 Correct 28 ms 8992 KB Output is correct
3 Correct 4 ms 9048 KB Output is correct
4 Correct 55 ms 8796 KB Output is correct
5 Correct 77 ms 8876 KB Output is correct
6 Correct 33 ms 8792 KB Output is correct
7 Correct 4 ms 9052 KB Output is correct
8 Correct 148 ms 9156 KB Output is correct
9 Correct 286 ms 23448 KB Output is correct
10 Correct 453 ms 54232 KB Output is correct
11 Correct 71 ms 8900 KB Output is correct
12 Correct 27 ms 8796 KB Output is correct
13 Correct 5 ms 9052 KB Output is correct
14 Correct 144 ms 8968 KB Output is correct
15 Correct 299 ms 25904 KB Output is correct
16 Correct 301 ms 51200 KB Output is correct
17 Correct 30 ms 8804 KB Output is correct
18 Correct 11 ms 9304 KB Output is correct
19 Correct 7 ms 9052 KB Output is correct
20 Correct 81 ms 9104 KB Output is correct
21 Correct 354 ms 37024 KB Output is correct
22 Correct 415 ms 63032 KB Output is correct