Submission #335752

#	Time	Username	Problem	Language	Result	Execution time	Memory
335752		ec1117	Factories (JOI14_factories)	C++17	0 / 100	16 ms	8044 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef vector<int> vi; 
typedef vector<pi> vpi;

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define bk back()
#define pb push_back

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define For(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define Rof(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define nl '\n' 

const int MOD = 1e9+7;
const ll INF = 1e18;
const int MX = 3e5+5;
const ld PI = acos((ld)-1);
mt19937 rng; // or mt19937_64
template<class T> bool ckmin(T& a, const T& b) { 
	return b < a ? a = b, 1 : 0; }
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down

void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << h; if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif

template<int SZ> struct Centroid{
	vpi adj[SZ];
	int lev[SZ], sub[SZ], par[SZ];
	ll dist[32][SZ], stor[SZ], anc[32][SZ];//todo anc
	bool done[SZ];
	vpi cur;
	
	void ae(int a, int b, int c){
		adj[a].pb(mp(b,c));
		adj[b].pb(mp(a,c));
	}
	void dfs(int x, int p){
		sub[x]=1;
		// int mx=0;
		trav(y,adj[x])if(y.f!=p && !done[y.f]){
			par[y.f]=x;
			dbg(x,y.f);
			dfs(y.f,x);
			sub[x]+=sub[y.f];
			// mx=max(mx,sub[y.f]);
		}
		// cur.pb(mp(mx,x));
	}
	int getCen(int x){
		// cur.clear();
		// dfs(x,x);
		// trav(y,cur){
		// 	dbg(x,y.f,y.s);
		// 	if(max(y.f,sub[x]-y.f)*2<=sub[x])
		// 		return y.s;
		// }
		// assert(false);
		dfs(x,x);
        int sz = sub[x];
        while (1) {
            pi mx = {0,0};
            for (pi i: adj[x]) if (!done[i.f] && i.f != par[x]) mx = max(mx,{sub[i.f],i.f});
            if (mx.f*2 > sz) x = mx.s;
            else return x;
        }
	}
	void genDist(int n, int par,int lev, ll d, int dad){
		dist[lev][n]=d;
		anc[lev][n]=dad;
		trav(x,adj[n])if(x.f!=par){
			genDist(x.f,n,lev,d+x.s,dad);	
		}
	}
	void gen(int CEN, int x){//CEN is prev cen
		x=getCen(x);done[x]=1;
		dbg(x);
		lev[x]=(CEN==-1?0:lev[CEN]+1);
		genDist(x,x,lev[x],0,x);

		trav(y,adj[x])if(!done[y.f])gen(x,y.f);

	}
	void init(int N){
		For(i,N)done[i]=false;
		For(i,N)stor[i]=INF;
		gen(-1,0);
	}

	void upd(int n, int t=1){
		For(i,lev[n]){
			if(t==1)ckmin(stor[anc[i][n]],dist[i][n]);
			else stor[anc[i][n]]=INF;
		}
	}
	ll query(int n){
		ll mn=INF;
		For(i,lev[n]){
			ckmin(mn, dist[i][n]+stor[anc[i][n]]);
		}
		return mn;
	}
};

Centroid<MX> C;
void Init(int N, int A[], int B[], int D[]){
	For(i,N-1){
		C.ae(A[i],B[i],D[i]);
	}
	C.init(N);
}

ll Query(int S, int X[], int T, int Y[]){
	ll mn=INF;
	For(i,S)C.upd(X[i]);
	For(i,T)ckmin(mn,C.query(Y[i]));
	For(i,S)C.upd(X[i],-1);
	return mn;
}

// int main(){
// 	int n,q;cin>> n>>q;
// 	int a[n],b[n],d[n];
// 	For(i,n-1){
// 		cin>>a[i];
// 		cin>>b[i];
// 		cin>>d[i];
// 	}
// 	dbg("HI");
// 	Init(n,a,b,d);
// }

Compilation message (stderr)

factories.cpp: In instantiation of 'void Centroid<SZ>::gen(int, int) [with int SZ = 300005]':
factories.cpp:107:3:   required from 'void Centroid<SZ>::init(int) [with int SZ = 300005]'
factories.cpp:130:10:   required from here
factories.cpp:44:18: warning: statement has no effect [-Wunused-value]
   44 | #define dbg(...) 0
      |                  ^
factories.cpp:97:3: note: in expansion of macro 'dbg'
   97 |   dbg(x);
      |   ^~~
factories.cpp: In instantiation of 'void Centroid<SZ>::dfs(int, int) [with int SZ = 300005]':
factories.cpp:79:3:   required from 'int Centroid<SZ>::getCen(int) [with int SZ = 300005]'
factories.cpp:96:5:   required from 'void Centroid<SZ>::gen(int, int) [with int SZ = 300005]'
factories.cpp:107:3:   required from 'void Centroid<SZ>::init(int) [with int SZ = 300005]'
factories.cpp:130:10:   required from here
factories.cpp:44:18: warning: statement has no effect [-Wunused-value]
   44 | #define dbg(...) 0
      |                  ^
factories.cpp:63:4: note: in expansion of macro 'dbg'
   63 |    dbg(x,y.f);
      |    ^~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67