Submission #852502

#	Time	Username	Problem	Language	Result	Execution time	Memory
852502		allin27x	Colors (RMI18_colors)	C++14	100 / 100	521 ms	75452 KiB

colors

#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 (stderr)

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 / 15
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 10 / 10
• Subtask 8: 22 / 22