Submission #246487

#	Time	Username	Problem	Language	Result	Execution time	Memory
246487		moonrabbit2	Logistical Metropolis (KRIII5_LM)	C++17	100 / 7	993 ms	64112 KiB

LM

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int> tii;
typedef tuple<ll,ll,ll> tll;
typedef tuple<int,int,int,int> ti4;
typedef vector<vector<ll>> mat;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<> gen(1,100); //gen(rng)
ll modinv(ll a,ll m){
	if(m==1) return 0;
	a%=m;
	if(a<0) a+=m;
	if(a==1) return 1;
	return m-modinv(m,a)*m/a;
}
template <int MOD_> struct modnum{
private:
	int v;
public:
	static const int MOD = MOD_;
 
	modnum() : v(0) {}
	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
	explicit operator int () const { return v; }
	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
	friend bool operator < (const modnum& a, const modnum& b) { return a.v < b.v; }
	friend bool operator <= (const modnum& a, const modnum& b) { return a.v <= b.v; }
	friend bool operator > (const modnum& a, const modnum& b) { return a.v > b.v; }
	friend bool operator >= (const modnum& a, const modnum& b) { return a.v >= b.v; }
 
	modnum operator ~ () const {
		modnum res;
		res.v = modinv(v, MOD);
		return res;
	}
 
	modnum& operator += (const modnum& o) {
		v += o.v;
		if (v >= MOD) v -= MOD;
		return *this;
	}
	modnum& operator -= (const modnum& o) {
		v -= o.v;
		if (v < 0) v += MOD;
		return *this;
	}
	modnum& operator *= (const modnum& o) {
		v = int(ll(v) * ll(o.v) % MOD);
		return *this;
	}
	modnum& operator /= (const modnum& o) {
		return *this *= (~o);
	}

	
	modnum operator-() const { return modnum(-v); }
	modnum& operator++() { return *this += 1; }
	modnum operator++(int){ modnum tmp=*this; ++*this; return tmp; }
	modnum& operator--() { return *this -= 1; }
	modnum operator--(int){ modnum tmp=*this; --*this; return tmp; }
 
	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
	friend modnum pow(modnum a, ll p) {
		modnum ans = 1;
		for (; p; p /= 2, a *= a) if (p&1) ans *= a;
		return ans;
	}
	friend ostream& operator<<(std::ostream& os, const modnum& o)
	{
		os << o.v;
		return os;
	}
	friend istream& operator>>(std::istream& is, modnum& o)
	{
		is >> o.v;
		return is;
	}
};
using mi=modnum<998244353>;
const ll mod=1e9+7,inf=1e18;
const int N=5e5+5,M=35,K=1e7+5;
int n,m,k,deg[N],in[N],out[N],cnt,h[N],p[17][N],mx[17][N];
int arr[N];
tii e[N],e2[N];
ll ans,cur;
vector<pii> g[N],E[N];
struct UF{
	int p[N]={0};
	int Fi(int x){
		if(!p[x]) return x;
		return p[x]=Fi(p[x]);
	}
	bool Un(int x,int y){
		x=Fi(x); y=Fi(y);
		if(x==y) return false;
		p[y]=x; return true;
	}
}U;
void dfs(int u){
	in[u]=++cnt;
	for(auto [v,c] : g[u]) if(v!=p[0][u]){
		h[v]=h[u]+1; p[0][v]=u; mx[0][v]=c; dfs(v);
	}
	out[u]=cnt;
}
int lca(int u,int v){
	if(h[u]>h[v]) swap(u,v);
	int d=h[v]-h[u];
	for(int bit=16;bit>=0;bit--) if(d&(1<<bit)) v=p[bit][v];
	if(u==v) return u;
	for(int bit=16;bit>=0;bit--) if(p[bit][u]!=p[bit][v]){
		u=p[bit][u]; v=p[bit][v];
	}
	return p[0][u];
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>m;
	for(int u,v,c,i=1;i<=m;i++){
		cin>>u>>v>>c;
		E[u].emplace_back(v,c);
		E[v].emplace_back(u,c);
		deg[u]++; deg[v]++;
		e[i]=tii(c,u,v);
	}
	sort(e+1,e+1+m);
	for(int i=1;i<=m;i++){
		auto [c,u,v]=e[i];
		if(!U.Un(u,v)) continue;
		ans+=c;
		g[u].emplace_back(v,c);
		g[v].emplace_back(u,c);
	}
	dfs(1);
	for(int bit=1;bit<17;bit++) for(int i=1;i<=n;i++){
		p[bit][i]=p[bit-1][p[bit-1][i]];
		mx[bit][i]=max(mx[bit-1][i],mx[bit-1][p[bit-1][i]]);
	}
	for(int i=1;i<=n;i++){
		k=0;
		arr[++k]=i;
		cur=ans;
		for(auto [v,c] : E[i]){
			arr[++k]=v;
		}
		sort(arr+1,arr+1+k,[](int a,int b){
			return in[a]<in[b];
		});
		for(int j=1;j<=deg[i];j++){
			arr[++k]=lca(arr[j],arr[j+1]);
		}
		sort(arr+1,arr+1+k,[](int a,int b){
			return in[a]<in[b];
		});
		k=unique(arr+1,arr+1+k)-arr-1;
		for(int j=1;j<=k;j++) U.p[arr[j]]=0;
		for(auto [v,c] : E[i]){
			U.Un(i,v);
			cur+=c;
		}
		stack<int> stk; stk.emplace(arr[1]);
		for(int j=2;j<=k;j++){
			int u=arr[j];
			while(in[u]<in[stk.top()]||out[stk.top()]<in[u]) stk.pop();
			int val=0,d=h[u]-h[stk.top()],v=u;
			for(int bit=16;bit>=0;bit--) if(d&(1<<bit)){
				val=max(val,mx[bit][v]); v=p[bit][v];
			}
			cur-=val;
			e2[j-1]=tii(val,u,stk.top());
			stk.emplace(u);
		}
		sort(e2+1,e2+k);
		for(int j=1;j<k;j++){
			auto [c,u,v]=e2[j];
			if(!U.Un(u,v)) continue;
			cur+=c;
		}
		cout<<cur<<"\n";
	}
	return 0;
}

Compilation message (stderr)

LM.cpp: In function 'int main()':
LM.cpp:154:16: warning: unused variable 'c' [-Wunused-variable]
   for(auto [v,c] : E[i]){
                ^

• Subtask 1: 28 / 28
• Subtask 2: 72 / 72