oj.uz

Submission #852499

# Submission time Handle Problem Language Result Execution time Memory
852499 2023-09-21T21:24:56 Z allin27x Colors (RMI18_colors) C++17
0 / 100
 14 ms 21852 KB 
#include <bits/stdc++.h>
using namespace std;

int a[(int)2e5];
int b[(int)2e5];
vector<int> adj[(int)2e5];
vector<pair<int,int>> mp[(int)2e5];

struct DSU{
	vector<int> sz, par, cm;
	stack<pair<int,int>> rb;
	DSU(int n){
		sz.resize(n,1); par.resize(n); iota(par.begin(), par.end(),0);
		cm.resize(n); for (int i=0; i<n; i++) cm[i] = a[i];
	}
	int get(int p) {
		return par[p] == p? p: get(par[p]);
	}
	void unite(int u, int v){
		u = get(u); v = get(v);
		if (u==v){
			rb.push({-1,-1}); return;
		}
		if (sz[u] > sz[v]) swap(u,v);
		rb.push({u, cm[v]});
		cm[v] = min(cm[v], cm[u]);
		sz[v] += sz[u];
		par[u] = v;
	}
	void rollback(){
		int u = rb.top().first; int m = rb.top().second; rb.pop();
		if (u==-1) return;
		int p = par[u];
		sz[p] -= sz[u];
		par[u] = u;
		cm[p] = m;
	}
};

struct SGT{
	vector<vector<pair<int,int>>> t;
	int R; DSU* dsu;
	SGT(int n){
		dsu = new DSU(n); 
		R = n-1; t.resize(4*n+7);
	}
	void add(int tl, int tr, int p, int l, int r, pair<int,int> e){
		if (l>r) return;
		if (tl==l && tr==r){
			t[p].push_back(e); return;
		}
		int tm = (tl+tr)/2;
		add(tl, tm, 2*p, l, min(r, tm), e);
		add(tm+1, tr, 2*p+1, max(tm+1, l), r, e);
	}
	void add(int l, int r, pair<int,int> e){
		add(0, R, 1, l, r, e);
	}
	void dfs(int l, int r, int p){
		for (auto [u,v]: t[p]) dsu->unite(u, v);
		if (l != r){
			int m = (l+r)/2;
			dfs(m+1, r, 2*p+1);
			dfs(l, m, 2*p);
		} else {
			for (auto [u,v]: mp[l]) a[u] = min(a[u], dsu->cm[dsu->get(u)]),
							   a[v] = min(a[v], dsu->cm[dsu->get(v)]);
		}
		for (auto [u,v]: t[p]) dsu->rollback();
	}
	void dfs(){
		dfs(0, R, 1);
	}
};

int solve(){
	int n,m; cin>>n>>m;
	vector<pair<int,int>> edges;
	for (int i=0; i<n; i++) adj[i].clear();
	for (int i=0; i<n; i++) cin>>a[i];
	for (int i=0; i<n; i++) cin>>b[i];
	for (int i=0; i<m; i++){
		int u,v; cin>>u>>v; u--; v--;
		adj[u].push_back(v); adj[v].push_back(u); edges.push_back({u,v});
	}
	for (int i=0; i<n; i++) if (b[i] > a[i]) return 0;
	SGT sgt(n);
	for (auto [u,v]: edges){
		int l1 = b[u], r1 = a[u], l2 = b[v], r2 = a[v];
		if (l1>l2) swap(l1,l2), swap(r1,r2);
		if (r1<l2) continue;
		sgt.add(max(l1, l2)-1, min(r1,r2)-1, {u,v});
		mp[max(l1,l2)-1].push_back({u,v});
	}
	sgt.dfs();
	for (int i=0; i<n; i++) if (a[i] != b[i]) return 0;
	return 1;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin>>t;
	while (t--){
		cout << solve() << '\n';
	}
}

Compilation message

colors.cpp: In member function 'void SGT::dfs(int, int, int)':
colors.cpp:69:13: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
   69 |   for (auto [u,v]: t[p]) dsu->rollback();
      |             ^~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 21564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 21564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 21564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -