oj.uz

Submission #130953

# Submission time Handle Problem Language Result Execution time Memory
130953 2019-07-16T10:03:06 Z DifferentHeaven Factories (JOI14_factories) C++11
100 / 100
 6211 ms 293748 KB 
#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

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24440 KB Output is correct
2 Correct 388 ms 35548 KB Output is correct
3 Correct 427 ms 35960 KB Output is correct
4 Correct 413 ms 35960 KB Output is correct
5 Correct 441 ms 36172 KB Output is correct
6 Correct 313 ms 35064 KB Output is correct
7 Correct 441 ms 35856 KB Output is correct
8 Correct 422 ms 35832 KB Output is correct
9 Correct 444 ms 36088 KB Output is correct
10 Correct 304 ms 35228 KB Output is correct
11 Correct 420 ms 35824 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24056 KB Output is correct
2 Correct 3546 ms 199376 KB Output is correct
3 Correct 4773 ms 244884 KB Output is correct
4 Correct 1397 ms 144244 KB Output is correct
5 Correct 5712 ms 293748 KB Output is correct
6 Correct 4707 ms 247172 KB Output is correct
7 Correct 1263 ms 79884 KB Output is correct
8 Correct 535 ms 68420 KB Output is correct
9 Correct 1659 ms 92536 KB Output is correct
10 Correct 1505 ms 80760 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24440 KB Output is correct
2 Correct 388 ms 35548 KB Output is correct
3 Correct 427 ms 35960 KB Output is correct
4 Correct 413 ms 35960 KB Output is correct
5 Correct 441 ms 36172 KB Output is correct
6 Correct 313 ms 35064 KB Output is correct
7 Correct 441 ms 35856 KB Output is correct
8 Correct 422 ms 35832 KB Output is correct
9 Correct 444 ms 36088 KB Output is correct
10 Correct 304 ms 35228 KB Output is correct
11 Correct 420 ms 35824 KB Output is correct
12 Correct 25 ms 24056 KB Output is correct
13 Correct 3546 ms 199376 KB Output is correct
14 Correct 4773 ms 244884 KB Output is correct
15 Correct 1397 ms 144244 KB Output is correct
16 Correct 5712 ms 293748 KB Output is correct
17 Correct 4707 ms 247172 KB Output is correct
18 Correct 1263 ms 79884 KB Output is correct
19 Correct 535 ms 68420 KB Output is correct
20 Correct 1659 ms 92536 KB Output is correct
21 Correct 1505 ms 80760 KB Output is correct
22 Correct 3496 ms 199928 KB Output is correct
23 Correct 3780 ms 203904 KB Output is correct
24 Correct 5241 ms 245732 KB Output is correct
25 Correct 5532 ms 249660 KB Output is correct
26 Correct 5224 ms 247300 KB Output is correct
27 Correct 6211 ms 291016 KB Output is correct
28 Correct 1430 ms 147340 KB Output is correct
29 Correct 5277 ms 246076 KB Output is correct
30 Correct 5494 ms 245740 KB Output is correct
31 Correct 5354 ms 247044 KB Output is correct
32 Correct 1447 ms 90844 KB Output is correct
33 Correct 527 ms 66276 KB Output is correct
34 Correct 994 ms 73464 KB Output is correct
35 Correct 996 ms 73832 KB Output is correct
36 Correct 1259 ms 75712 KB Output is correct
37 Correct 1288 ms 75756 KB Output is correct