关于重复计算
查看原帖
关于重复计算
126972
Kevinx楼主2024/8/9 13:05

简单来说就是把答案的计算方式换了一下,但是重复计算了一些答案。

把

.
	aans[u] += 1ll*siz[v] * (n - siz[v]);
.
.
	if(vis[u] == 0) ans[u] = 1ll*(n-1);
	else ans[u] += 1ll*(n-sum-1);
.
.
.
	ans[i] = 1ll*2*ans[i];
	cout << ans[i] << "\n"; 

改为

.
	ans[u] += 1ll*siz[v] * (n - siz[v]);
.
.
	if(vis[u] == 0) ans[u] = 1ll*2*(n-1);
	else ans[u] += 1ll*(n-sum-1)*(sum+1)+1ll*(n-1);
.
.
.
	cout << ans[i] << "\n"; 

就过了

30pts

#include<bits/stdc++.h>
#define ll long long
#define Mid ll mid = (l+r)>>1
using namespace std;
const int N = 5e5 + 20;
ll n, m, tot = 0;
ll cnt = 1, h[N], siz[N], ans[N];
ll low[N], dfn[N];
bool vis[N];
struct graph{
	ll v, nxt;
}e[N<<1];

void add_edge(ll u, ll v) {
	e[++cnt] = (graph){v, h[u]};
	h[u] = cnt;
}
void tarjan(ll u, ll inid) {
	low[u] = dfn[u] = ++tot;
	siz[u] = 1;
	ll son = 0, sum = 0;
	for(int i = h[u]; i; i = e[i].nxt) {
		ll v = e[i].v;
		if(i == (inid^1)) continue;
		
		if(!dfn[v]) {
			tarjan(v, i);
			siz[u] += siz[v];
			low[u] = min(low[u], low[v]);
			if(low[v] >= dfn[u]) {
			sum += siz[v];
			son++;
			ans[u] += 1ll*siz[v] * (n - siz[v]);
			if(u!=1 || son > 1) vis[u] = 1;
		}
			
		}
		else low[u] = min(low[u], dfn[v]);
	}
	if(vis[u] == 0) ans[u] = 1ll*(n-1);
	else ans[u] += 1ll*(n-sum-1);
}
int main(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		ll u, v;
		cin >> u >> v;
		add_edge(u, v);
		add_edge(v, u);
	}
	tarjan(1, 0);
	for(int i = 1; i <= n; i++) {
		ans[i] = 1ll*2*ans[i];
		cout << ans[i] << "\n"; 
	}
	return  0;
} 

100pts

#include<bits/stdc++.h>
#define ll long long
#define Mid ll mid = (l+r)>>1
using namespace std;
const int N = 5e5 + 20;
ll n, m, tot = 0;
ll cnt = 1, h[N], siz[N], ans[N];
ll low[N], dfn[N];
bool vis[N];
struct graph{
	ll v, nxt;
}e[N<<1];

void add_edge(ll u, ll v) {
	e[++cnt] = (graph){v, h[u]};
	h[u] = cnt;
}
void tarjan(ll u, ll inid) {
	low[u] = dfn[u] = ++tot;
	siz[u] = 1;
	ll son = 0, sum = 0;
	for(int i = h[u]; i; i = e[i].nxt) {
		ll v = e[i].v;
		if(i == (inid^1)) continue;
		
		if(!dfn[v]) {
			tarjan(v, i);
			siz[u] += siz[v];
			low[u] = min(low[u], low[v]);
			if(low[v] >= dfn[u]) {
			sum += siz[v];
			son++;
			ans[u] += 1ll*siz[v] * (n - siz[v]);
			if(u!=1 || son > 1) vis[u] = 1;
		}
			
		}
		else low[u] = min(low[u], dfn[v]);
		
	
		
		
	}
	
	if(vis[u] == 0) ans[u] = 1ll*2*(n-1);
	else {
		ans[u] += 1ll*(n-sum-1)*(sum+1)+1ll*(n-1);
	}
}
int main(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		ll u, v;
		cin >> u >> v;
		add_edge(u, v);
		add_edge(v, u);
	}
	tarjan(1, 0);
	for(int i = 1; i <= n; i++) {
		cout << ans[i] << "\n"; 
	}
	return  0;
} 
2024/8/9 13:05
加载中...