oj.uz

Submission #1039760

# Submission time Handle Problem Language Result Execution time Memory
1039760 2024-07-31T08:34:40 Z Name(#11031) Petrol stations (CEOI24_stations) C++17
8 / 100
 838 ms 31804 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=array<int,2>;
using tii=array<int,3>;
using tll=array<ll,3>;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int N=70005;
int n,k;
vector<pii> g[N];
int sz[N],vis[N],sub[N],p[16][N],up[N],val[N];
ll cttl,csub[N],cnt[N];
int m; ll D[N],P[N];
vector<int> V,C[N];
vector<pii> vals;
vector<tll> dists;
ll d[N],st[N],dp[N];
ll ans[N];
struct FEN{
	ll F[N];
	int n;
	void init(int n_){
		n=n_;
		for(int i=0;i<=n;i++) F[i]=0;
	}
	void add(int i,ll v){
		for(;i<=n;i+=i&-i) F[i]+=v;
	}
	ll qry(int i){
		ll r=0;
		for(;i;i-=i&-i) r+=F[i];
		return r;
	}
}F;
void dfsSize(int u,int p){
	sz[u]=1;
	for(auto [v,w]: g[u]) if(!vis[v]&&p!=v){
		dfsSize(v,u);
		sz[u]+=sz[v];
	}
}
int findCentroid(int u,int p,int S){
	for(auto [v,w]: g[u]) if(!vis[v]&&p!=v&&sz[v]>=S) return findCentroid(v,u,S);
	return u;
}
void dfs(int u){
	V.push_back(u);
	C[u].clear();
	dp[u]=1;
	D[++m]=d[u]-1;
	for(auto [v,w]: g[u]) if(!vis[v]&&p[0][u]!=v){
		p[0][v]=u;
		for(int i=1;i<=15;i++) p[i][v]=p[i-1][p[i-1][v]];
		sub[v]=sub[u];
		if(!p[0][u]) sub[v]=v;
		d[v]=d[u]+w;
		st[v]=k-w;
		dfs(v);
	}
	if(d[u]>k){
		int v=u;
		for(int i=15;i>=0;i--) if(d[u]-d[p[i][v]]<=k) v=p[i][v];
		val[u]=val[v];
		dp[v]+=dp[u];
		up[u]=v;
		C[v].push_back(u);
	} else{
		up[u]=0;
		val[u]=k-d[u];
	}
	vals.push_back({val[u],u});
	if(p[0][u]){
		dists.push_back({d[u]-1,u,1});
		dists.push_back({d[p[0][u]]-1,u,-1});
	}
	csub[u]=cnt[u]=0;
}
void dfs2(int u){
	P[u]=F.qry(lower_bound(D+1,D+m+1,d[u]-1)-D);
	cnt[u]+=P[u]-P[p[0][u]];
	F.add(lower_bound(D+1,D+m+1,d[u]+st[u])-D,cnt[u]);
	for(auto [v,w]: g[u]) if(!vis[v]&&p[0][u]!=v){
		dfs2(v);
	}
	F.add(lower_bound(D+1,D+m+1,d[u]+st[u])-D,-cnt[u]);
}
void solve(int r){
	dfsSize(r,0);
	r=findCentroid(r,0,(sz[r]+1)/2);
	for(int i=0;i<=15;i++) p[i][r]=0;
	d[r]=0;
	sub[r]=0;
	vals.clear();
	dists.clear();
	V.clear();
	m=0;
	P[r]=0;
	dfsSize(r,0);
	dfs(r);
	D[++m]=1e18;
	sort(D+1,D+m+1);
	m=unique(D+1,D+m+1)-D-1;
	sort(vals.begin(),vals.end());
	sort(dists.begin(),dists.end());
	cttl=0;
	for(int i=0,j=0;i<(int)dists.size();i++){
		while(j<(int)vals.size()&&vals[j][0]<=dists[i][0]){
			cttl++;
			csub[sub[vals[j][1]]]++;
			j++;
		}
		cnt[dists[i][1]]+=dists[i][2]*(cttl-csub[sub[dists[i][1]]]);
	}
	F.init(m);
	for(auto [v,w]: g[r]) if(!vis[v]) dfs2(v);
	debug(r);
	for(int u: V){
		ans[u]+=(dp[u]-1)*((ll)V.size()-sz[sub[u]]-(u==r));
		debug(u,dp[u],V.size(),sz[sub[u]],cnt[u]);
		if(u!=r) ans[p[0][u]]+=cnt[u]*sz[u];
	}
	vis[r]=1;
	for(auto [v,w]: g[r]) if(!vis[v]) solve(v);
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>k;
	for(int u,v,w,i=1;i<n;i++){
		cin>>u>>v>>w;
		u++; v++;
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}
	solve(1);
	for(int i=1;i<=n;i++) cout<<ans[i]<<"\n";
	return 0;
}

Compilation message

Main.cpp: In function 'void solve(int)':
Main.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 42
      |                    ^~
Main.cpp:123:2: note: in expansion of macro 'debug'
  123 |  debug(r);
      |  ^~~~~
Main.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 42
      |                    ^~
Main.cpp:126:3: note: in expansion of macro 'debug'
  126 |   debug(u,dp[u],V.size(),sz[sub[u]],cnt[u]);
      |   ^~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14168 KB Output is correct
2 Correct 2 ms 14168 KB Output is correct

Subtask #1
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14168 KB Output is correct
2 Correct 2 ms 14168 KB Output is correct
3 Correct 4 ms 14172 KB Output is correct
4 Correct 5 ms 14432 KB Output is correct
5 Incorrect 5 ms 14428 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14172 KB Output is correct
2 Correct 808 ms 31804 KB Output is correct

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14168 KB Output is correct
2 Correct 2 ms 14168 KB Output is correct
3 Correct 2 ms 14172 KB Output is correct
4 Correct 808 ms 31804 KB Output is correct
5 Incorrect 838 ms 31216 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14168 KB Output is correct
2 Correct 2 ms 14168 KB Output is correct
3 Incorrect 448 ms 27908 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14168 KB Output is correct
2 Correct 2 ms 14168 KB Output is correct
3 Incorrect 448 ms 27908 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14168 KB Output is correct
2 Correct 2 ms 14168 KB Output is correct
3 Correct 4 ms 14172 KB Output is correct
4 Correct 5 ms 14432 KB Output is correct
5 Incorrect 5 ms 14428 KB Output isn't correct
6 Halted 0 ms 0 KB -