oj.uz

Submission #852486

# Submission time Handle Problem Language Result Execution time Memory
852486 2023-09-21T21:12:12 Z allin27x Colors (RMI18_colors) C++17
7 / 100
 122 ms 14532 KB 
#include <bits/stdc++.h>
using namespace std;

int a[(int)2e5];
int b[(int)2e5];
vector<int> adj[(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);
		} 
		for (auto [u,v]: t[p]) 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});
	}
	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:66:13: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
   66 |   for (auto [u,v]: t[p]) dsu->rollback();
      |             ^~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 11172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5880 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 11328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 11328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 11172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 122 ms 14532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 5716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 11172 KB Output isn't correct
2 Halted 0 ms 0 KB -