社区讨论

即将破防

TTiat_Siba_Ignareo
学术版参与者 42已保存回复 225

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
225 条
当前快照
1 份
快照标识符
@ltsp3l5e
此快照首次捕获于
2024/03/15 21:29
2 年前
此快照最后确认于
2024/07/18 14:47
2 年前
查看原帖
求调几道题。

P4652

CPP
#include<bits/stdc++.h>
using namespace std;
#define mxn 214514
int low[mxn], dfn[mxn], col[mxn], f[mxn], ndfn[mxn], el[mxn], er[mxn];
int n, m, cnt, ccnt, ncnt;
bool vis[mxn];
vector<int> G[mxn], NG[mxn];
stack<int> s;
void tarjan(int u, int f){
	dfn[u] = low[u] = ++cnt;
	s.push(u);
	vis[u] = 1;
	for (auto &v : G[u]){
		if (v == f)
			continue;
		if (!dfn[v]){
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
		}else if (vis[v])
			low[u] = min(low[u], dfn[v]);
	}
	if (dfn[u] == low[u]){
		ccnt++;
		while (!s.empty()){
			int v = s.top();
			s.pop();
			vis[v] = 0;
			col[v] = ccnt;
			if (u == v)
				break;
		}
	}
}
void dfs(int u){
	ndfn[u] = ++ncnt;
	for (auto v : NG[u])
		if (!ndfn[v]){
			dfs(v);
			f[u] += f[v];
		}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
		el[i] = u;
		er[i] = v;
	}
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			tarjan(i, 0); 
	for (int i = 1; i <= n; i++)
		for (auto v : G[i])
			if (col[i] != col[v]){
				NG[col[i]].push_back(col[v]);
				NG[col[v]].push_back(col[i]); 
			}
	int q;
	cin >> q;
	while (q--){
		int u, v;
		cin >> u >> v;
		f[col[u]]++;
		f[col[v]]--;
	}
	for (int i = 1; i <= ccnt; i++)
		if (!ndfn[i])
			dfs(i);
	for (int i = 1; i <= m; i++){
		int u = col[el[i]], v = col[er[i]];
		if (u == v)
			cout << "B";
		else{
			if (ndfn[u] > ndfn[v]){
				if (f[u] > 0)
					cout << "R";
				else if (f[u] == 0)
					cout << "B";
				else
					cout << "L";
			}else if (ndfn[u] < ndfn[v]){
				if (f[v] < 0)
					cout << "R";
				else if (f[v] == 0)
					cout << "B";
				else
					cout << "L";
			}
		}
	}
}

P6381

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, k, cnt, ans;
int in[214514], srt[214514];
struct node
{
	public:
		int v, w, l, nx;
		bool operator <(node b)const
		{
			return this->v < b.v;
		}
};
node G[114514<<1];
queue<int>q;
int a[214514], ccnt, pos[214514];
bool vis[214514];
int h[214514];
int ec;
void addedge(int u, int v, int w, int l)
{
	G[++ec].v = v;
	G[ec].w = w;
	G[ec].l = l;
	G[ec].nx = h[u];
	h[u] = ec;
}
void sieve(int n)
{
	for(int i = 2; i <= n; i++)
	{
		if(!vis[i])
		{
			a[++ccnt] = i;
			pos[i] = ccnt;
		}
		for(int j = 1; j <= ccnt; j++)
		{
			if(i * a[j] > n)
				break;
			vis[i * a[j]] = 1;
			pos[i * a[j]] = j;
			if(i % a[j] == 0)
				break;
		}
	}
}
const int mod[] = {1145141, 19260818 - 1};
int d[114514<<1], dd[114514<<1];
int dc;
int hsh(int x){
	long long res = 0;
	for(int i = 0; i < dc; i++)
		if(dd[i])
			res = (res + d[i] ^ 11451419ll + dd[i] ^ 114514ll) % mod[x];  
	return res;
}
int hs[114514<<1][2], p[114514<<1][2];
void init(){
	for(int i = 1; i <= m; i++)
	{
		memset(d, 0, sizeof d);
		memset(dd, 0, sizeof dd);
		dc=0;
		for(int e = G[i].w, pr = 0; e != 1; e /= a[pos[e]]){
			if(pr == pos[e])
			{
				if(++dd[dc - 1] == k)
					dd[dc - 1] = 0;
				else{
					d[++dc] = pos[e];
					dd[dc] = (k != 1);
					pr = pos[e];
				}
			}
		}
		hs[i][0] = hsh(0);
		hs[i][1] = hsh(1);
	    for (int j = 0; j < dc; j++) 
			if (dd[j])
				dd[j] = k - dd[j];
	    p[i][0] = hsh(0);
	    p[i][1] = hsh(1);
	}
}
struct noode{
	public:
		int h,hh;
};
map<node,int>f[114514<<1];
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 1; i <= m; i++)
	{
		int u, v, w, l;
		cin >> u >> v >> w >> l;
		addedge(u, v, w, l);
		in[v]++;
	}
	sieve(100000);
	for(int i = 1; i <= m; i++)
		if(!in[i])
			q.push(i);
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		srt[++cnt] = u;
		for(int e = h[u]; e; e = G[e].nx)
		{
			int v = G[e].v;
			in[v]--;
			if(!in[v])
				q.push(v);
		}
	}
	init();
	node k, j;
	for(int i = n; i; i--)
	{
		int u = srt[i];
		for(int e = h[u]; e; e = G[e].nx){
			int v = G[e].v;
			k = {hs[e][0], hs[e][1]};
			f[u][k] = max(f[u][k], G[e].l);
			j = {p[e][0], p[e][1]};
			f[u][k] = max(f[u][k], G[e].l + f[v][j]);
			ans = max(ans, f[u][k]);
		}
	}
	cout << ans << "\n";
}

CF487E

CPP
#include<bits/stdc++.h>
using namespace std;
int dfn[100005], low[100005];
int n, m, a1, a2, cnt, ign, ans, ccnt, qq;
vector<int> G[100005], BCC[100005], CST[150000];
stack<int> s;
queue<int> q;
void tarjan(int u){
	dfn[u] = low[u] = ++cnt;
	int sn = 0;
	s.push(u);
	for (auto &v : G[u]){
		if (!dfn[v]){
			sn++;
			tarjan(v);
			low[u] = min(low[u], low[v]);
			if (low[v] >= dfn[u]){
				ccnt++;
				while (!s.empty()){
					int vv = s.top();
					s.pop();
					CST[n + ccnt].push_back(vv);
					CST[vv].push_back(n + ccnt);
					BCC[ccnt].push_back(vv);
				//	cerr << vv << "<->" << n + ccnt << "\n";
					if (v == vv)
						break;
				}
				BCC[ccnt].push_back(u);
				CST[n + ccnt].push_back(u);
            	CST[u].push_back(n + ccnt);
			//	cerr << u << "<->" << n + ccnt << "\n";
			}
		}else
			low[u] = min(low[u], dfn[v]);
	}
}
int a[150005];
int fa[150005],hs[150000],sz[150000],top[150000],ddfn[150000],rdfn[150000],dep[150000];
int vst;
void dfs(int u,int fat) {
	fa[u]=fat;
	sz[u]=1;
	dep[u]=dep[fat]+1;
	for(auto &v:CST[u]) {
		if(v==fat)continue;
		dfs(v,u);
		sz[u]+=sz[v];
		if(sz[v]>sz[hs[u]])hs[u]=v;
	}
}
void cut(int u,int tp) {
	ddfn[u]=++vst;
	rdfn[vst]=u;
	top[u]=tp;
	if(hs[u]) {
		cut(hs[u],tp);
		for(auto &v:G[u])if(v!=fa[u]&&v!=hs[u])cut(v,v);
	}
}
int trr[400020];
void pup(int u) {
	trr[u]=min(trr[u<<1],trr[u<<1|1]);
}
void build(int u,int le,int ri) {
	if(le==ri) {
		trr[u]=a[rdfn[le]];
		return;
	}
	int mid=(le+ri)>>1;
	build(u<<1,le,mid);
	build(u<<1|1,mid+1,ri);
	pup(u);
}
bool inr(int le,int ri,int L,int R) {
	return (L<=le)&&(ri<=R);
}
bool otr(int le,int ri,int L,int R) {
	return (le>R)||(ri<L);
}
long long query(int u,int le,int ri,int L,int R) {
//	cout << trr[u] << "\n";
	if(inr(le,ri,L,R))return trr[u];
	else if(!otr(le,ri,L,R)) {
		int mid=(le+ri)>>1;
		return min(query(u<<1,le,mid,L,R),query(u<<1|1,mid+1,ri,L,R));
	}
	return INT_MAX;
}
long long qry(int x,int y) {
	long long ans=INT_MAX;
	while(top[x]!=top[y]) {
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ans=min(ans,query(1,1,n+ccnt,ddfn[top[x]],ddfn[x]));
		x=fa[top[x]];
	}
	return min(ans,query(1,1,n+ccnt,min(ddfn[x],ddfn[y]),max(ddfn[x],ddfn[y])));
}
void update(int u,int le,int ri,int ft,long long x) {
	int mid=(le+ri)>>1;
	if(le==ri){
		trr[u]=x;
		return;
	}
	if(ft<=mid)update(u<<1,le,mid,ft,x);
	else update(u<<1|1,mid+1,ri,ft,x);
	pup(u);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m >> qq;
	for(int i=1; i<=n; i++)cin>>a[i];
	for (int i = 1; i <= m; i++){
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for (int i = 1; i <= n; i++)
		if (!dfn[i]){
			tarjan(i);
			s.pop();
		}
	for (int i = n + 1; i <= n + ccnt; i++)
		a[i] = INT_MAX;
	int r = 1;
	for(int i=1;i<=n+ccnt;i++)sort(CST[i].begin(),CST[i].end(),[](int x,int y){return a[x]<a[y];});
	dfs(r,0);
	cut(r,0);
	build(1,1,n+ccnt);
	while(qq--) {
		string ord;
		cin>>ord;
		if(ord=="C"){
			int u,v;
			cin>>u>>v;
			update(1,1,n+ccnt,ddfn[u],v);
		}else if(ord=="A"){
			int u,v;
			cin>>u>>v;
			long long ans = qry(u, v);
			for (auto w : CST[u])
				if (w > n){
					for (auto x : BCC[w - n])
						if (x != u){
						//	cout << x << "\n";
							ans = min(ans, qry(x, x));
						}
				}
			for (auto w : CST[v])
				if (w > n){
					for (auto x : BCC[w - n])
						if (x != v)
							ans = min(ans, qry(x, x));
				}
			cout<<ans<<'\n';
		}
	}
}

回复

共 225 条回复，欢迎继续交流。

正在加载回复...