이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 500000
#define LOG 20
#define INF 1000000000000000000
using namespace std;
///ifstream cin ("c.in");
///ofstream cout ("c.out");
vector <pair<int, long long>> graph[MAX + 10], length[MAX + 10];
vector <int> nodes, v;
int timer = 1, level[MAX + 10], in[MAX + 10], ancestor[LOG + 10][MAX + 10], company[MAX + 10], visited[MAX + 10];
long long dist[MAX + 10], dp1[MAX + 10], dp2[MAX + 10], ans;
///int a[MAX + 10], b[MAX + 10], d[MAX + 10], x[MAX + 10], y[MAX + 10];
void dfs(int node, int parent)
{
in[node] = timer;
timer++;
level[node] = level[parent] + 1;
ancestor[0][node] = parent;
for (auto next : graph[node])
if (next.first != parent)
{
dist[next.first] = dist[node] + next.second;
dfs(next.first, node);
}
}
void Init(int n, int a[], int b[], int d[])
{
for (int i = 0; i < n - 1; i++)
{
graph[a[i] + 1].push_back({b[i] + 1, d[i]});
graph[b[i] + 1].push_back({a[i] + 1, d[i]});
}
dfs(1, 0);
for (int p = 1; p <= LOG; p++)
for (int node = 1; node <= n; node++)
ancestor[p][node] = ancestor[p - 1][ancestor[p - 1][node]];
for (int node = 1; node <= n; node++)
{
dp1[node] = INF;
dp2[node] = INF;
}
}
bool cmp(int i, int j)
{
return (in[i] < in[j]);
}
int lca(int node1, int node2)
{
if (level[node1] < level[node2])
swap(node1, node2);
int diff = level[node1] - level[node2];
for (int p = LOG; p >= 0; p--)
if (diff >> p & 1)
node1 = ancestor[p][node1];
if (node1 == node2)
return node1;
for (int p = LOG; p >= 0; p--)
if (ancestor[p][node1] != 0 && ancestor[p][node2] != 0)
if (ancestor[p][node1] != ancestor[p][node2])
{
node1 = ancestor[p][node1];
node2 = ancestor[p][node2];
}
return ancestor[0][node1];
}
void solve(int node)
{
if (company[node] == 1)
dp1[node] = 0;
if (company[node] == 2)
dp2[node] = 0;
for (auto next : length[node])
{
solve(next.first);
dp1[node] = min(dp1[node], dp1[next.first] + next.second);
dp2[node] = min(dp2[node], dp2[next.first] + next.second);
}
ans = min(ans, dp1[node] + dp2[node]);
}
long long Query(int s, int x[], int t, int y[])
{
for (int i = 0; i < s; i++)
{
visited[x[i] + 1] = 1;
company[x[i] + 1] = 1;
nodes.push_back(x[i] + 1);
}
for (int i = 0; i < t; i++)
{
visited[y[i] + 1] = 1;
company[y[i] + 1] = 2;
nodes.push_back(y[i] + 1);
}
sort(nodes.begin(), nodes.end(), cmp);
for (int i = 1; i < nodes.size(); i++)
if (visited[lca(nodes[i - 1], nodes[i])] == 0)
{
visited[lca(nodes[i - 1], nodes[i])] = 1;
nodes.push_back(lca(nodes[i - 1], nodes[i]));
}
sort(nodes.begin(), nodes.end(), cmp);
for (auto node : nodes)
{
if (!v.empty())
{
while (!v.empty() && lca(node, v.back()) != v.back())
v.pop_back();
length[v.back()].push_back({node, dist[node] + dist[v.back()] - 2 * dist[lca(node, v.back())]});
}
v.push_back(node);
}
ans = INF;
solve(v[0]);
for (int i = 0; i < s; i++)
company[x[i] + 1] = 0;
for (int i = 0; i < t; i++)
company[y[i] + 1] = 0;
for (auto node : nodes)
{
dp1[node] = INF;
dp2[node] = INF;
visited[node] = 0;
length[node].clear();
}
nodes.clear();
v.clear();
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for (int i = 1; i < nodes.size(); i++)
| ~~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |