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 |
댓글 없음:
댓글 쓰기