제출 #445204

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
445204		Tizariox	경주 (Race) (IOI11_race)	C++14	21 / 100	3061 ms	25556 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using pii = pair<int, int>;
 
#define MOD 1000000007
#define nl "\n"
#define pb push_back
 
int n, k;
vector<pii> adjLists[200000];
int par[200000];
int subTreeSize[200000];
bool vis[200000];
 
int dist[200000];
int anc[200000][19];
 
void findAncestors() {
	for (int i = 0; i < n; i++) {
		if (dist[i] != 0) {
			anc[i][0] = par[i];
		}
	}
	for (int j = 1; j <= 18; j++) {
		for (int i = 0; i < n; i++) {
			if (dist[i] != 0) {
				anc[i][j] = anc[anc[i][j - 1]][j - 1];
			}
		}
	}
}
 
void treeDfs2(int node, int prevNode) {
	for (int i = 0; i < adjLists[node].size(); i++) {
		if (adjLists[node][i].first != prevNode) {
			pii child = adjLists[node][i];
			par[child.first] = node;
			dist[child.first] = dist[node] + 1;
			treeDfs2(child.first, node);
		}
	}
}
 
int lca(int a, int b) {
	if (dist[a] > dist[b]) { // swap if a is further
		return lca(b, a);
	}
	if (dist[a] < dist[b]) { // find ancestor of b that's the same depth as a
		for (int k = 18; dist[b] != dist[a]; k--) {
			while (dist[b] - (1 << k) >= dist[a]) {
				b = anc[b][k];
			}
		}
	}
	for (int k = 18; k > 0; k--) {
		while (anc[a][k] != anc[b][k]) {
			a = anc[a][k];
			b = anc[b][k];
		}
	}
	while (a != b) {
		a = par[a];
		b = par[b];
	}
	return a;
}
 
int distance(int a, int b) {
	int ancestor = lca(a, b);
	return dist[a] + dist[b] - 2 * dist[ancestor];
}
 
void calcSubtrees(int node) {
	for (pii i : adjLists[node]) {
		if (i.first != par[node]) {
			calcSubtrees(i.first);
			subTreeSize[node] += subTreeSize[i.first];
		}
	}
}
 
unordered_set<int> visited;
 
int findCentroid(int node) {
	// we don't need to worry about the parent and its subtrees because we
	// already know it's not a centroid
	visited.insert(node);
	for (pii i : adjLists[node]) {
		if (visited.count(i.first) == 0) {
			if (subTreeSize[i.first] * 2 > n) {
				return findCentroid(i.first);
			} else {
				return node;
			}
		}
	}
	return -1;
}
 
int minOverallPath = 1e9;
int minPath;
 
void treeDfs1(int node, int path, int root) {
	if (path == k) {
		minPath = min(minPath, distance(node, root));
		return;
	}
	visited.insert(node);
	for (int i = 0; i < adjLists[node].size(); i++) {
		pii child = adjLists[node][i];
		if (visited.count(child.first) > 0 || vis[child.first]) {
			continue;
		}
		treeDfs1(child.first, path + child.second, root);
	}
}
 
unordered_map<int, pii> nodeDists;
queue<pair<int, pii>> nodeDistsQueue;
 
void treeDfs3(int node, int path, int root) {
	if (nodeDists.find(path) != nodeDists.end()) {
		if (distance(node, root) < (*nodeDists.find(path)).second.second) {
			nodeDists[path] = pii(distance(node, root), node);
		} 
	} else {
		nodeDistsQueue.push(make_pair(path, pii(distance(node, root), node)));
		if (nodeDists.find(k - path) != nodeDists.end()) {
			minPath = min(minPath, distance(node, root) + distance((*nodeDists.find(k - path)).second.second, root));
		}
	}
	visited.insert(node);
	for (int i = 0; i < adjLists[node].size(); i++) {
		pii child = adjLists[node][i];
		if (visited.count(child.first) > 0 || vis[child.first]) {
			continue;
		}
		treeDfs3(child.first, path + child.second, root);
	}
}
 
void decomp(int node) {
	int centroid = findCentroid(node);
	vis[centroid] = true;
	minPath = 1e9;
	treeDfs1(centroid, 0, centroid);
	visited.clear();
	for (pii i : adjLists[centroid]) {
		if (vis[i.first]) {
			continue;
		}
		treeDfs3(i.first, i.second, centroid);
		visited.clear();
		while (!nodeDistsQueue.empty()) {
			nodeDists.insert(nodeDistsQueue.front());
			nodeDistsQueue.pop();
		}
	}
	nodeDists.clear();
	minOverallPath = min(minOverallPath, minPath);
	for (pii i : adjLists[centroid]) {
		if (!vis[i.first]) {
			decomp(i.first);
		}
	}
}

int best_path(int n1, int k1, int inputs[][2], int l[]) {
  n = n1;
  k = k1;
  for (int i = 0; i < n - 1; i++) {
  	adjLists[inputs[i][0]].pb(pii(inputs[i][1], l[i]));
	adjLists[inputs[i][1]].pb(pii(inputs[i][0], l[i]));
  }
  	treeDfs2(0, -1);
	findAncestors();
	calcSubtrees(0);
	decomp(0);
	return ((minOverallPath == 1e9) ? -1 : minOverallPath);
}
 
#ifdef LOCAL
int inputs[200000][2];
int l[200000];
int main() {
  	freopen("grader.in.5", "r", stdin);
    freopen("out.txt", "w", stdout);
  int n1, k1;
	cin >> n1 >> k1;
	for (int i = 0; i < n1 - 1; i++) {
      	cin >> inputs[i][0] >> inputs[i][1] >> l[i];
	}
  cout << best_path(n1, k1, inputs, l) << "\n";
}
#endif

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

race.cpp: In function 'void treeDfs2(int, int)':
race.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for (int i = 0; i < adjLists[node].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void treeDfs1(int, int, int)':
race.cpp:112:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |  for (int i = 0; i < adjLists[node].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void treeDfs3(int, int, int)':
race.cpp:136:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |  for (int i = 0; i < adjLists[node].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57