oj.uz

Submission #851805

# Submission time Handle Problem Language Result Execution time Memory
851805 2023-09-20T16:13:53 Z TimDee Colors (RMI18_colors) C++17
61 / 100
 539 ms 75600 KB 
//  Esti <3

//\
     šťastia pre nás :)
//   you're already the best
//             _
//   ^ ^      //
// >(O_O)<___//
//   \ __ __  \
//    \\ \\ \\\\
 
#include <bits/stdc++.h>
using namespace std;
 
//#pragma GCC optimize("O3","unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#pragma GCC optimize("O3")
#pragma GCC target("popcnt")

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() {
		if (!rb.size()) exit(0);
		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;
		}
	}

	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:36:1: warning: multi-line comment [-Wcomment]
   36 | // \
      | ^
colors.cpp: In member function 'void sgt::go(long long int)':
colors.cpp:111:13: warning: unused variable 'x' [-Wunused-variable]
  111 |    for(auto&x:t[v]) dsu.roll();
      |             ^
colors.cpp: In function 'void solve()':
colors.cpp:161:9: warning: unused variable 'v' [-Wunused-variable]
  161 |     int v = e.s, j = e.s;
      |         ^
colors.cpp:170:9: warning: unused variable 'v' [-Wunused-variable]
  170 |     int v = e.s, j = e.s;
      |         ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 11092 KB Output is correct
2 Correct 24 ms 11096 KB Output is correct
3 Correct 4 ms 11352 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 21596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 10844 KB Output is correct
2 Correct 32 ms 10844 KB Output is correct
3 Correct 4 ms 11100 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 10844 KB Output is correct
2 Correct 32 ms 10844 KB Output is correct
3 Correct 4 ms 11100 KB Output is correct
4 Correct 148 ms 10964 KB Output is correct
5 Correct 313 ms 33912 KB Output is correct
6 Correct 539 ms 75600 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 11092 KB Output is correct
2 Correct 24 ms 11096 KB Output is correct
3 Correct 4 ms 11352 KB Output is correct
4 Correct 68 ms 10844 KB Output is correct
5 Correct 32 ms 10844 KB Output is correct
6 Correct 4 ms 11100 KB Output is correct
7 Correct 72 ms 10992 KB Output is correct
8 Correct 29 ms 10844 KB Output is correct
9 Correct 5 ms 11356 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 11140 KB Output is correct
2 Correct 334 ms 37200 KB Output is correct
3 Correct 327 ms 65556 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 21852 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 11092 KB Output is correct
2 Correct 24 ms 11096 KB Output is correct
3 Correct 4 ms 11352 KB Output is correct
4 Runtime error 12 ms 21596 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -