oj.uz

Submission #941801

# Submission time Handle Problem Language Result Execution time Memory
941801 2024-03-09T12:52:59 Z KiaRez Colors (RMI18_colors) C++17
100 / 100
 582 ms 82612 KB 
/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 3e5+23, lg = 18;
ll Mod = 1e9+7; //998244353;

inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

int t, n, m, a[N], b[N], mark[N], vis[N], par[N], sz[N], cnt[N];
vector<int> adj[N], seg[2*N], veca[N], vecb[N], rolbak;

int getPar(int v) {return (par[v]==0 ? v : getPar(par[v]));}
void merge(int v, int u) {
	v = getPar(v), u=getPar(u);
	if(v == u) return;
	if(sz[v] < sz[u]) swap(v,u);
	sz[v] += sz[u];
	par[u] = v;
	rolbak.pb(u);
}

void rbk(int x) {
	while(size(rolbak) > x) {
		int v = rolbak.back();
		rolbak.pop_back();
		sz[par[v]] -= sz[v];
		par[v] = 0;
	}
}

void add(int l, int r, int v, int ind=1, int lc=1, int rc=(1<<lg)+1) {
	if(l>=rc || lc>=r) return;
	if(lc>=l && rc<=r) {
		seg[ind].pb(v);
		return;
	}
	int mid = (lc+rc)/2;
	add(l, r, v, 2*ind, lc, mid);
	add(l, r, v, 2*ind+1, mid, rc);
}

void dfs(int ind=1, int lc=1, int rc=(1<<lg)+1) {
	int tmp = size(rolbak);
	for(auto it : seg[ind]) {
		mark[it] = 1;
		for(auto it2 : adj[it]) {
			if(mark[it2] == 1) merge(it, it2);
		}
	}
	if(ind >= (1<<lg)) {
		int id = ind-(1<<lg)+1;
		for(auto it : veca[id]) {cnt[getPar(it)] ++;}
		for(auto it : vecb[id]) {
			if(cnt[getPar(it)] > 0) vis[it] = 1;
		}
		for(auto it : veca[id]) cnt[getPar(it)] --;
	} else {
		int mid = (lc+rc)/2;
		dfs(2*ind, lc, mid);
		if(mid<=n) dfs(2*ind+1, mid, rc);
	}
	rbk(tmp);
	for(auto it : seg[ind]) mark[it] = 0;
}

void solve() {
	cin>>n>>m;
	fill(sz, sz+n+1, 1);
	for(int i=1; i<=n; i++) cin>>a[i];
	for(int i=1; i<=n; i++) cin>>b[i];
	for(int v,u,i=1; i<=m; i++) {
		cin>>v>>u;
		adj[v].pb(u);
		adj[u].pb(v);
	}
	for(int i=1; i<=n; i++) {
		if(a[i] < b[i]) {cout<<0<<endl; return;}
		add(b[i], a[i]+1, i);
		vecb[b[i]].pb(i);
		veca[a[i]].pb(i);
	}
	dfs(1);
	for(int i=1; i<=n; i++) {
		if(vis[i] == 0) {
			cout<<0<<endl; return ;
		}
	}
	cout<<1<<endl;
}

/*
int t, n, m, a[N], b[N], mark[N], vis[N], par[N], sz[N], cnt[N];
vector<int> adj[N], seg[2*N], veca[N], vecb[N], rolbak;
*/
void clearseg(int ind=1, int lc=1, int rc=(1<<lg)+1) {
	seg[ind].clear();
	if(ind<(1<<lg)) {
		int mid = (lc+rc)/2;
		clearseg(2*ind, lc, mid);
		if(mid<=n) clearseg(2*ind+1, mid, rc);
	}
}

void reset() {
	for(int i=0; i<=n+1; i++) {
		mark[i] = vis[i] = par[i] = sz[i] = cnt[i] = 0;
		adj[i].clear();
		veca[i].clear();
		vecb[i].clear();
	}
	rolbak.clear();
	clearseg(1);
}

int main () {
	ios_base::sync_with_stdio(false), cin.tie(0);

	cin>>t;
	while(t--) {
		solve();
		reset();
	}

	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 41716 KB Output is correct
2 Correct 31 ms 41560 KB Output is correct
3 Correct 13 ms 41816 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 41560 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 41564 KB Output is correct
2 Correct 32 ms 41560 KB Output is correct
3 Correct 13 ms 41816 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 41564 KB Output is correct
2 Correct 32 ms 41560 KB Output is correct
3 Correct 13 ms 41816 KB Output is correct
4 Correct 152 ms 41712 KB Output is correct
5 Correct 334 ms 57680 KB Output is correct
6 Correct 582 ms 77332 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 41716 KB Output is correct
2 Correct 31 ms 41560 KB Output is correct
3 Correct 13 ms 41816 KB Output is correct
4 Correct 74 ms 41564 KB Output is correct
5 Correct 32 ms 41560 KB Output is correct
6 Correct 13 ms 41816 KB Output is correct
7 Correct 72 ms 41760 KB Output is correct
8 Correct 31 ms 41564 KB Output is correct
9 Correct 13 ms 41820 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 41972 KB Output is correct
2 Correct 313 ms 57916 KB Output is correct
3 Correct 404 ms 77124 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 41564 KB Output is correct
2 Correct 16 ms 41564 KB Output is correct
3 Correct 14 ms 41564 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 41716 KB Output is correct
2 Correct 31 ms 41560 KB Output is correct
3 Correct 13 ms 41816 KB Output is correct
4 Correct 52 ms 41560 KB Output is correct
5 Correct 74 ms 41564 KB Output is correct
6 Correct 32 ms 41560 KB Output is correct
7 Correct 13 ms 41816 KB Output is correct
8 Correct 152 ms 41712 KB Output is correct
9 Correct 334 ms 57680 KB Output is correct
10 Correct 582 ms 77332 KB Output is correct
11 Correct 72 ms 41760 KB Output is correct
12 Correct 31 ms 41564 KB Output is correct
13 Correct 13 ms 41820 KB Output is correct
14 Correct 147 ms 41972 KB Output is correct
15 Correct 313 ms 57916 KB Output is correct
16 Correct 404 ms 77124 KB Output is correct
17 Correct 31 ms 41564 KB Output is correct
18 Correct 16 ms 41564 KB Output is correct
19 Correct 14 ms 41564 KB Output is correct
20 Correct 63 ms 43920 KB Output is correct
21 Correct 311 ms 61724 KB Output is correct
22 Correct 504 ms 82612 KB Output is correct