oj.uz

Submission #852502

# Submission time Handle Problem Language Result Execution time Memory
852502 2023-09-21T21:27:00 Z allin27x Colors (RMI18_colors) C++14
100 / 100
 521 ms 75452 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++) mp[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:60:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |   for (auto [u,v]: t[p]) dsu->unite(u, v);
      |             ^
colors.cpp:66:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |    for (auto [u,v]: mp[l]) a[u] = min(a[u], dsu->cm[dsu->get(u)]),
      |              ^
colors.cpp:69:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |   for (auto [u,v]: t[p]) dsu->rollback();
      |             ^
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();
      |             ^~~~~
colors.cpp: In function 'int solve()':
colors.cpp:89:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |  for (auto [u,v]: edges){
      |            ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 16976 KB Output is correct
2 Correct 21 ms 12376 KB Output is correct
3 Correct 4 ms 11356 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 11600 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 17164 KB Output is correct
2 Correct 23 ms 12380 KB Output is correct
3 Correct 5 ms 11096 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 17164 KB Output is correct
2 Correct 23 ms 12380 KB Output is correct
3 Correct 5 ms 11096 KB Output is correct
4 Correct 137 ms 23732 KB Output is correct
5 Correct 311 ms 35284 KB Output is correct
6 Correct 503 ms 67424 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 16976 KB Output is correct
2 Correct 21 ms 12376 KB Output is correct
3 Correct 4 ms 11356 KB Output is correct
4 Correct 63 ms 17164 KB Output is correct
5 Correct 23 ms 12380 KB Output is correct
6 Correct 5 ms 11096 KB Output is correct
7 Correct 62 ms 18684 KB Output is correct
8 Correct 23 ms 12376 KB Output is correct
9 Correct 5 ms 11352 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 20164 KB Output is correct
2 Correct 298 ms 37396 KB Output is correct
3 Correct 331 ms 55440 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 11600 KB Output is correct
2 Correct 15 ms 11608 KB Output is correct
3 Correct 7 ms 11096 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 16976 KB Output is correct
2 Correct 21 ms 12376 KB Output is correct
3 Correct 4 ms 11356 KB Output is correct
4 Correct 58 ms 11600 KB Output is correct
5 Correct 63 ms 17164 KB Output is correct
6 Correct 23 ms 12380 KB Output is correct
7 Correct 5 ms 11096 KB Output is correct
8 Correct 137 ms 23732 KB Output is correct
9 Correct 311 ms 35284 KB Output is correct
10 Correct 503 ms 67424 KB Output is correct
11 Correct 62 ms 18684 KB Output is correct
12 Correct 23 ms 12376 KB Output is correct
13 Correct 5 ms 11352 KB Output is correct
14 Correct 120 ms 20164 KB Output is correct
15 Correct 298 ms 37396 KB Output is correct
16 Correct 331 ms 55440 KB Output is correct
17 Correct 30 ms 11600 KB Output is correct
18 Correct 15 ms 11608 KB Output is correct
19 Correct 7 ms 11096 KB Output is correct
20 Correct 83 ms 14396 KB Output is correct
21 Correct 299 ms 43528 KB Output is correct
22 Correct 521 ms 75452 KB Output is correct