Submission #130953

#	Time	Username	Problem	Language	Result	Execution time	Memory
130953		DifferentHeaven	Factories (JOI14_factories)	C++11	100 / 100	6211 ms	293748 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
#define ii pair <int, long long>
#define x first
#define y second
#define db(x) cerr << #x << " = " << x << endl;
#define _ << ", " << 

using namespace std;

inline void read(int &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void read(long long &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void writeln(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar('\n');}
inline void write(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar(' ');}

const int N = 5e5 + 7;
const int LOG = log2(N) + 1;
const long long oo = 1e18 + 7;

int n, q, nNode, Time, root = -1;
long long dist;
int nChild[N], d[N];
int p[N][LOG + 7];
bool blocked[N];
vector <ii> adj[N];
int t[N];
long long f[N];
vector <long long> D[N];
int par[N];

void DFS(int u){
	for (auto t: adj[u]){
		int v = t.x;
		int w = t.y;
		if (!d[v]){
			d[v] = d[u] + 1;
			p[v][0] = u;
			DFS(v);
		}
	}
}

void dfs(int u, int p){
	nNode++;
	nChild[u] = 1;
	for (auto t: adj[u]){
		int v = t.x;
		if (v != p && !blocked[v]){
			dfs(v, u);
			nChild[u] += nChild[v];
		}
	}
}

inline int getCentroid(int u, int p){
	for (auto t: adj[u]){
		int v = t.x;
		int w = t.y;
		if (v != p && !blocked[v])
			if (nChild[v] > nNode / 2){
				dist += w;
				return getCentroid(v, u);
			}
	}	
	return u;
}

inline void updateDist(int u, int p, long long d){
	for (auto t: adj[u]){
		int v = t.x;
		int w = t.y;
		if (v != p && !blocked[v]){
			D[v].push_back(d + w);
			updateDist(v, u, d + w);
		}
	}
}

inline void buildTree(int u, int p, int c, int dd){
	nNode = 0;
	dfs(u, u);

	dist = dd;
	int centroid = getCentroid(u, p);

	if (root == -1) 
		root = centroid;
	
	par[centroid] = c;

	blocked[centroid] = true;

	updateDist(centroid, centroid, 0);

	for (auto t: adj[centroid]){
		int v = t.x;
		int w = t.y;
		if (v != p && !blocked[v])
			buildTree(v, centroid, centroid, w);
	}
}

void Init(int pN, int pA[], int pB[], int pD[]){
	n = pN;
	for (int i = 0; i < n - 1; i++){
		int u = pA[i];
		int v = pB[i];
		int w = pD[i];
		adj[u].push_back(ii(v, w));
		adj[v].push_back(ii(u, w));
	}
	d[0] = 1;
	DFS(0);
	buildTree(0, -1, -1, 0);

	for (int j = 1; j <= LOG; j++)
		for (int i = 0; i < n; i++)
			p[i][j] = p[p[i][j - 1]][j - 1];

	for (int i = 0; i < n; i++)
		D[i].push_back(0);
}

inline void Update(int x){
	int savex = x;
	int id = D[x].size() - 1;
	while (1){
		if (t[x] != Time) {
			f[x] = oo;
			t[x] = Time;
		}
		f[x] = min(f[x], D[savex][id]);
		int pp = par[x];
		if (pp == -1) break;
		x = pp;
		id--;
	}
}

inline long long Get(int x){
	int savex = x;
	long long res = oo;
	int id = D[x].size() - 1;
	while (1){
		if (t[x] != Time){
			f[x] = oo;
			t[x] = Time;
		}
		res = min(res, D[savex][id] + f[x]);
		int pp = par[x];
		if (pp == -1) break;
		x = pp;
		id--;
	}
	return res;
}

long long Query(int S, int X[], int T, int Y[]){
	++Time;
	for (int i = 0; i < S; i++)
		Update(X[i]);

	long long res = oo;

	for (int i = 0; i < T; i++)
		res = min(res, Get(Y[i]));
	
	return res;
}

// int X[N], Y[N];

// int main(){
// 	ios_base::sync_with_stdio(false);
// 	cin.tie(nullptr);
// 	freopen("test.inp", "r", stdin);
// 	freopen("test.out", "w", stdout);
	
// 	read(n); read(q);
// 	for (int i = 1; i < n; i++){
// 		int u, v, w;
// 		read(u); read(v); read(w);
// 		adj[u].push_back(ii(v, w));
// 		adj[v].push_back(ii(u, w));
// 	}

// 	// d[0] = 1;
// 	// DFS(0);
// 	// buildTree(0, -1, -1, 0);

// 	// for (int j = 1; j <= LOG; j++)
// 	// 	for (int i = 0; i < n; i++)
// 	// 		p[i][j] = p[p[i][j - 1]][j - 1];

// 	// for (int i = 0; i < n; i++)
// 	// 	D[i].push_back(0);

// 	for (int i = 1; i <= q; i++){
// 		int S, T;
// 		read(S); read(T);
// 		for (int j = 0; j < S; j++)
// 			read(X[j]);
// 		for (int j = 0; j < T; j++)
// 			read(Y[j]);
// 		writeln(Query(S, X, T, Y));
// 	}
// }

Compilation message (stderr)

factories.cpp: In function 'void DFS(int)':
factories.cpp:34:7: warning: unused variable 'w' [-Wunused-variable]
   int w = t.y;
       ^

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