关于神奇CE
  • 板块灌水区
  • 楼主Tony2
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/7/5 19:10
  • 上次更新2023/11/4 18:35:26
查看原帖
关于神奇CE
171288
Tony2楼主2021/7/5 19:10

一份代码,用c++编译超时,用c++17编译正常,会是什么原因?

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5, M = 3e5+5, Q = 5e5+5;
int n, log2n, m, q;
int fa[N], top[N], tot, t[N<<1];
int num[N], ak[Q];
int dfsnum, pl[N<<1], pr[N<<1], rev[N<<1], f[N<<1][22];
vector<int> e[N<<1];
pair<int, int> edge[M];
bool vis[N<<1]; 
vector<pair<int, int> > vec;
struct tree{
#define mid ((l+r)>>1)
#define ls (now<<1)
#define rs (now<<1|1)
	pair<int, int> a[N<<2];
	void up(int now){
		a[now] = max(a[ls], a[rs]);
	}
	void build(int now, int l, int r){
		if (l == r){
			a[now] = make_pair(num[rev[l]], l);
			return;
		}
		build(ls, l, mid);
		build(rs, mid+1, r);
		up(now);
	}
	void change(int now, int l, int r, int s, int k){
		if (l == r){
			a[now].first = k;
			return;
		}
		if (s <= mid) change(ls, l, mid, s, k);
		else change(rs, mid+1, r, s, k);
		up(now);
	}
	pair<int, int> ask(int now, int l, int r, int s, int t){
		if (s <= l && r <= t)
			return a[now];
		pair<int, int> res(0, 0);
		if (s <= mid) res = max(ask(ls, l, mid, s, t), res);
		if (t > mid) res = max(ask(rs, mid+1, r, s, t), res);
		return res;
	}
#undef mid
#undef ls
#undef rs
}T;
int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
void dfs(int u){
	if (u <= n) rev[dfsnum+1] = u;
	pl[u] = u<=n?++dfsnum:dfsnum+1;
	for (int i = 1; i <= log2n; i++)
		f[u][i] = f[f[u][i-1]][i-1];
	for (int i = 0; i < e[u].size(); i++){
		int v = e[u][i];
		f[v][0] = u;
		dfs(v);
	}
	pr[u] = dfsnum;
}
int main(){
	std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	cout << sizeof(num)+sizeof(ak)+sizeof(e)+sizeof(edge)+sizeof(f)+sizeof(fa)+sizeof(pl)+sizeof(pr)+sizeof(rev)+sizeof(t)+sizeof(top)+sizeof(vis)+sizeof(T) << endl;
	cin >> n >> m >> q;
	log2n = log2(n);
	for (int i = 1; i <= n; i++)
		cin >> num[i];
	for (int i = 1; i <= m; i++){
		int u, v;
		cin >> u >> v;
		edge[i] = make_pair(u, v);
	}
	for (int i = 1; i <= q; i++){
		int opt;
		cin >> opt;
		if (opt == 1)
			cin >> ak[i];
		else{
			int id;
			cin >> id;
			vis[id] = 1;
			vec.push_back(make_pair(id, i));
		}
	}
	for (int i = 1; i <= m; i++)
		if (!vis[i])
			vec.push_back(make_pair(i, q+1));
	for (int i = 1; i <= n; i++)
		fa[i] = i, top[i] = i, t[i] = q+1;
	tot = n;
	for (int i = vec.size()-1; i >= 0; i--){
		int u = edge[vec[i].first].first, v = edge[vec[i].first].second;
		u = getfa(u), v = getfa(v);
		if (u == v) continue;
		fa[u] = v;
		e[++tot].push_back(top[u]);
		e[tot].push_back(top[v]);
		top[v] = tot;
		t[tot] = vec[i].second;
	}
	memset(vis, 0, sizeof(vis));
	tot++;
	for (int i = 1; i <= n; i++){
		int u = getfa(i);
		if (!vis[top[u]]){
			vis[top[u]] = 1;
			e[tot].push_back(top[u]); 
		}
	}
	dfs(tot);
	T.build(1, 1, n);
	for (int i = 1; i <= q; i++){
		if (!ak[i]) continue;
		int u = ak[i], _t = i;
		for (int j = log2n; j >= 0; j--)
			if (t[f[u][j]] >= _t)
				u = f[u][j];
		pair<int, int> res = T.ask(1, 1, n, pl[u], pr[u]);
		T.change(1, 1, n, res.second, 0);
		cout << res.first << endl;
	}
	return 0;
}
2021/7/5 19:10
加载中...