3176 도로 네트워크 https://www.acmicpc.net/problem/3176
Codeforces #425 (Div. 2) D - Misha, Grisha and Underground
http://codeforces.com/contest/832/problem/D
LCA (최소 공통 조상)
어떤 두 정점의 가장 가까운 공통 루트가 누구인지 알아내는 문제이다.
종만북에는 세그먼트 트리로 LCA를 구하지만 넘 복잡하고 보통 DP를 이용해서 구한다.
DFS로 노드들의 depth를 구한 후 $2^K$위의 루트 노드가 무엇인지 DP를 이용하여 전처리한다.
여기서 정점사이의 거리나 최소거리 등의 정보도 함께 넣을 수 있다.
1. 정점들의 거리
트리에서 두 정점 사이의 거리를 구하는 문제이다.
전처리 할 때 현재 노드에서 $2^K$위의 루트 노드 까지 거리도 전처리 해준다.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 987654321
int N, M;
vector<pair<int, int>> adj[40001];
bool visit[40001];
int depth[40001], par[40001][17], dist[40001][17];
void dfs(int here, int d){
visit[here] = true;
depth[here] = d;
for (auto n : adj[here]){
int next = n.second;
int cost = n.first;
if (!visit[next]){
par[next][0] = here;
dist[next][0] = cost;
dfs(next, d + 1);
}
}
}
void dp(){
for (int m = 1; m < 17; m++){
for (int n = 1; n <= N; n++){
par[n][m] = par[par[n][m - 1]][m - 1];
dist[n][m] = dist[n][m - 1] + dist[par[n][m - 1]][m - 1];
}
}
}
int lca(int u, int v){
int ret = 0;
if (depth[u] < depth[v]) swap(u, v);
for (int i = 16; i >= 0; i--){
if (depth[u] - depth[v] >= (1 << i)){
ret += dist[u][i];
u = par[u][i];
}
}
//depth같아짐
if (u == v) return ret;
for (int i = 16; i >= 0; i--){
if (par[u][i] != par[v][i]){
ret += (dist[u][i] + dist[v][i]);
u = par[u][i], v = par[v][i];
}
}
ret += (dist[u][0] + dist[v][0]);
return ret;
}
int main(){
scanf("%d", &N);
for (int n = 0; n < N - 1; n++){
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
adj[u].push_back({ d, v });
adj[v].push_back({ d, u });
}
//전처리
dfs(1, 0);
dp();
scanf("%d", &M);
while (M--){
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", lca(a, b));
}
return 0;
}
| cs |
2. 도로 네트워크
문제를 잘 읽어보면 네트워크는 트리형태이다.
이 문제에서는 최소 간선, 최대 간선에 대해 전처리 해주면 된다.
문제를 잘 읽어보면 네트워크는 트리형태이다.
이 문제에서는 최소 간선, 최대 간선에 대해 전처리 해주면 된다.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 987654321
int N, K;
vector<pair<int, int>> adj[100001];
bool visit[100001];
int depth[100001];
int par[100001][21];
int edge_min[100001][21], edge_max[100001][21];
void dfs(int here, int d){
visit[here] = true;
depth[here] = d;
for (auto n : adj[here]){
int next = n.second;
int cost = n.first;
if (!visit[next]){
par[next][0] = here;
edge_min[next][0] = cost;
edge_max[next][0] = cost;
dfs(next, d + 1);
}
}
}
void dp(){
for (int n = 1; n < 21; n++){
for (int m = 1; m <= N; m++){
par[m][n] = par[par[m][n - 1]][n - 1];
edge_min[m][n] = min(edge_min[m][n - 1], edge_min[par[m][n - 1]][n - 1]);
edge_max[m][n] = max(edge_max[m][n - 1], edge_max[par[m][n - 1]][n - 1]);
}
}
}
pair<int,int> lca(int a, int b){
int rmin = INF, rmax = -INF;
if (depth[a] < depth[b]) swap(a, b);
for (int i = 20; i >= 0; i--){
if (depth[a] - depth[b] >= (1 << i)){
rmin = min(rmin, edge_min[a][i]);
rmax = max(rmax, edge_max[a][i]);
a = par[a][i];
}
}
if (a == b) return { rmin, rmax };
for (int i = 20; i >= 0; i--){
if (par[a][i] != par[b][i]){
rmin = min(rmin, min(edge_min[a][i], edge_min[b][i]));
rmax = max(rmax, max(edge_max[a][i], edge_max[b][i]));
a = par[a][i];
b = par[b][i];
}
}
rmin = min(rmin, min(edge_min[a][0], edge_min[b][0]));
rmax = max(rmax, max(edge_max[a][0], edge_max[b][0]));
return { rmin, rmax };
}
int main(){
scanf("%d", &N);
for (int n = 0; n < N - 1; n++){
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
adj[u].push_back({ d, v });
adj[v].push_back({ d, u });
}
//전처리
dfs(1, 0);
dp();
scanf("%d", &K);
for (int k = 0; k < K; k++){
int D, E;
scanf("%d%d", &D, &E);
pair<int,int> ans = lca(D, E);
printf("%d %d\n", ans.first, ans.second);
}
return 0;
}
| cs |
3. Codeforces #425 (Div. 2) - D
나의 첫 codeforces 대회였다.
2시간이라는 촉박한 시간과 영어여서 문제이해하는데도 한참 걸렸다.
(그리고 Div. 2 치고 어렵게 나온거같다;; 1문제 품)
B는 문자열, C는 수식과 실수가 나와서 바로넘어갔었다.
D를 실제로 C보다 더 많이 풀었는데 대회때는 못풀었지만 그나마 풀만했던거같다.
트리가 존재한다. Misha는 $s$->$f$를 가며 정점에 낙서를 하고 Grisha는 $f$->$t$를 이동하며
낙서된 정점의 수를 세는데 Grisha가 세는 정점의 수의 최댓값을 구하는 문제이다.
각 쿼리에는 $s$, $f$, $t$의 후보 $a$, $b$, $c$가 주어진다.
대회때는 2820 자동차 공장풀듯이 세그먼트트리와 lazy propogation 그리고 LCA를 이용해서 풀려고 했지만 끝나고서야 오류를 알았다.
사실은 LCA만으로 풀리는 문제이다.
1. LCA($s$, $f$) == LCA($f$, $t$) == $f$인 경우
2. LCA($s$, $f$) == LCA($f$, $t$) != $f$인 경우
3. LCA($s$, $f$) != LCA($f$, $t$)인 경우에 대해 따져주면 된다.
쿼리에서 입력으로 들어오는 후보가 3개밖에없으니 $3!$으로 모든 경우에 대해 돌려주어 최댓값을 구하면 된다.
int solve(int s, int f, int t) {
int ret = 0;
int sf_lca = getLCA(s, f), ft_lca = getLCA(f, t);
if (sf_lca == ft_lca && sf_lca == f) ret = depth[getLCA(s, t)] - depth[f];
else if (sf_lca == ft_lca) {
int common_lca = sf_lca;
ret = depth[getLCA(s, t)] - depth[common_lca] + depth[f] - depth[common_lca];
}
else{
if (depth[sf_lca] > depth[ft_lca]) ret = depth[f] - depth[sf_lca];
else ret = 0;
}
return ret + 1;
}
| cs |
