Submission #44258

#	Time	Username	Problem	Language	Result	Execution time	Memory
44258		szawinis	Factories (JOI14_factories)	C++17	15 / 100	6041 ms	284040 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e17;
 
int n;
vector<int> sz;
vector<vector<pair<int,int> > > g;
vector<vector<int> > anc;
vector<vector<ll> > d;
vector<bool> block;
vector<ll> mn;

void init_dfs(int u, int par) {
	sz[u] = 1;
	for(auto p: g[u]) {
		int v, w; tie(v, w) = p;
		if(block[v] || v == par) continue;
		init_dfs(v, u);
		sz[u] += sz[v];
	}
}

void calc(int src) {
	init_dfs(src, -1);
	int cen = src;
	while(true) {
		bool found = false;
		for(auto p: g[cen]) if(sz[p.first] < sz[cen] && sz[p.first] << 1 >= sz[src]) {
			cen = p.first;
			found = true;
			break;
		}
		if(!found) break;
	}
	block[cen] = true;

	queue<pair<int, int> > q;
	q.emplace(cen, -1);
	d[cen].push_back(0);
	anc[cen].push_back(cen);
	while(!q.empty()) {
		int u, par; tie(u, par) = q.front();
		q.pop();
		for(auto p: g[u]) if(p.first != par && !block[p.first]) {
			d[p.first].push_back(d[u].back() + p.second);
			anc[p.first].push_back(cen);
			q.emplace(p.first, u);
		}
	}

	for(auto p: g[cen]) if(!block[p.first]) calc(p.first);
}
 
void Init(int N, int A[], int B[], int D[]) {
	n = N;
	g.resize(n), sz.resize(n), anc.resize(n), d.resize(n), block.resize(n);
	mn.assign(n, INF);
	for(int i = 0; i < n-1; i++) {
		g[A[i]].emplace_back(B[i], D[i]);
		g[B[i]].emplace_back(A[i], D[i]);
	}
	calc(0);
}
 
ll Query(int S, int X[], int T, int Y[]) {
	ll ret = INF;
	for(int i = 0; i < S; i++) for(int j = 0; j < anc[X[i]].size(); j++)
		mn[anc[X[i]][j]] = min(d[X[i]][j], mn[anc[X[i]][j]]);
	for(int i = 0; i < T; i++) for(int j = 0; j < anc[Y[i]].size(); j++)
		ret = min(mn[anc[Y[i]][j]] + d[Y[i]][j], ret);
	for(int i = 0; i < S; i++) for(int j = 0; j < anc[X[i]].size(); j++)
		mn[anc[X[i]][j]] = INF;
	return ret;
}

Compilation message (stderr)

factories.cpp: In function 'll Query(int, int*, int, int*)':
factories.cpp:69:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < S; i++) for(int j = 0; j < anc[X[i]].size(); j++)
                                            ~~^~~~~~~~~~~~~~~~~~
factories.cpp:71:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < T; i++) for(int j = 0; j < anc[Y[i]].size(); j++)
                                            ~~^~~~~~~~~~~~~~~~~~
factories.cpp:73:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < S; i++) for(int j = 0; j < anc[X[i]].size(); j++)
                                            ~~^~~~~~~~~~~~~~~~~~

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