제출 #74089

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
74089		shoemakerjo	공장들 (JOI14_factories)	C++14	15 / 100	8087 ms	261956 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pil pair<int, ll>

#define maxn 500010
int n;
vector<vector<int>> adj(maxn);
vector<vector<ll>> adjd(maxn);

//run a centroid decomposition


int subsize[maxn];
bool marked[maxn];
ll dr[19][maxn]; 
ll mycomp[19][maxn]; //which component i am in (specify by centroid is good)
ll curdist[maxn];
int cp[maxn];

ll inf = 1LL << 60;
ll curmin[maxn]; //for the queries
int cl;
int cc;

void dfs(int u, int p, bool op = false) {

	cp[u] = p;
	subsize[u] = 1;
	if (op) {
		// cout << u << " is in " << cc << " at level " << cl << endl;
		dr[cl][u] = curdist[u];
		mycomp[cl][u] = cc;
	}
	for (int i = 0; i < adj[u].size(); i++)  {
		int nx = adj[u][i];
		if (nx == p || marked[nx]) continue;
		curdist[nx] = curdist[u] + adjd[u][i];

		dfs(nx, u, op);
		subsize[u] += subsize[nx];
	}
}

int getcentroid(int u, int csize) {
	curdist[u] = 0LL;
	dfs(u, -1);
	int cur = u;
	bool fin = false;
	while (!fin) {
		fin = true;
		for (int nx : adj[cur]) {
			if (marked[nx] || nx == cp[cur]) continue;
			if (subsize[nx] > csize/2) {
				fin = false;
				cur = nx;
				break;
			}
		}	
	}
	return cur;

}

void go(int u, int csize, int level) {
	int cen = getcentroid(u, csize);
	curdist[cen] = 0LL;
	cc = cen;
	cl = level;
	dfs(cen, -1, true);
	marked[cen] = true;
	for (int cur : adj[cen]) {
		if (!marked[cur])
			go(cur, subsize[cur], level+1);
	}

}

void Init(int N, int A[], int B[], int D[]) {
	for (int i = 0; i < 19; i++) {
		fill(mycomp[i], mycomp[i]+maxn, -1);
	}
	n = N;
	for (int i = 0; i < N-1; i++) {
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
		adjd[A[i]].push_back(D[i]);
		adjd[B[i]].push_back(D[i]);
	}
	fill(curmin, curmin+maxn, inf);
	go(0, n, 0);
}

ll Query(int S, int X[], int T, int Y[]) {
	ll ans = inf;
	for (int i = 0; i < S; i++) {
		int val = X[i];
		for (int j = 0; j < 19; j++) {
			if (mycomp[j][val] == -1) break;
			curmin[mycomp[j][val]] = 
				min(curmin[mycomp[j][val]], dr[j][val]);
		}
	}

	for (int i = 0; i < T; i++) {
		int val = Y[i];
		for (int j = 0; j < 19; j++) {
			if (mycomp[j][val] == -1) break;

			ans = min(ans, 
				curmin[mycomp[j][val]] + dr[j][val]);
		}
	}

	for (int i = 0; i < S; i++) {
		int val = X[i];
		for (int j = 0; j < 19; j++) {
			if (mycomp[j][val] == -1) break;
			curmin[mycomp[j][val]] = inf;
		}
	}

  	return ans;
}

//COULD NOT SUBMIT AT TIME FIRST SOLVED

컴파일 시 표준 에러 (stderr) 메시지

factories.cpp: In function 'void dfs(int, int, bool)':
factories.cpp:37:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < adj[u].size(); i++)  {
                  ~~^~~~~~~~~~~~~~~

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