oj.uz

답안 #752314

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
752314 2023-06-02T17:53:30 Z anaduguleanu 공장들 (JOI14_factories) C++14
100 / 100
 6925 ms 187724 KB 
#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;
}

Compilation message

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++)
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 24368 KB Output is correct
2 Correct 1150 ms 33128 KB Output is correct
3 Correct 1471 ms 33384 KB Output is correct
4 Correct 1242 ms 33228 KB Output is correct
5 Correct 894 ms 33404 KB Output is correct
6 Correct 884 ms 33100 KB Output is correct
7 Correct 1524 ms 33132 KB Output is correct
8 Correct 1269 ms 33356 KB Output is correct
9 Correct 912 ms 33292 KB Output is correct
10 Correct 925 ms 33188 KB Output is correct
11 Correct 1511 ms 33164 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 24148 KB Output is correct
2 Correct 2262 ms 122980 KB Output is correct
3 Correct 3883 ms 127424 KB Output is correct
4 Correct 1258 ms 138884 KB Output is correct
5 Correct 2000 ms 180472 KB Output is correct
6 Correct 4250 ms 147412 KB Output is correct
7 Correct 3579 ms 66924 KB Output is correct
8 Correct 1471 ms 66188 KB Output is correct
9 Correct 2320 ms 73176 KB Output is correct
10 Correct 4209 ms 68184 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 24368 KB Output is correct
2 Correct 1150 ms 33128 KB Output is correct
3 Correct 1471 ms 33384 KB Output is correct
4 Correct 1242 ms 33228 KB Output is correct
5 Correct 894 ms 33404 KB Output is correct
6 Correct 884 ms 33100 KB Output is correct
7 Correct 1524 ms 33132 KB Output is correct
8 Correct 1269 ms 33356 KB Output is correct
9 Correct 912 ms 33292 KB Output is correct
10 Correct 925 ms 33188 KB Output is correct
11 Correct 1511 ms 33164 KB Output is correct
12 Correct 16 ms 24148 KB Output is correct
13 Correct 2262 ms 122980 KB Output is correct
14 Correct 3883 ms 127424 KB Output is correct
15 Correct 1258 ms 138884 KB Output is correct
16 Correct 2000 ms 180472 KB Output is correct
17 Correct 4250 ms 147412 KB Output is correct
18 Correct 3579 ms 66924 KB Output is correct
19 Correct 1471 ms 66188 KB Output is correct
20 Correct 2320 ms 73176 KB Output is correct
21 Correct 4209 ms 68184 KB Output is correct
22 Correct 4668 ms 157616 KB Output is correct
23 Correct 4332 ms 158784 KB Output is correct
24 Correct 5314 ms 162032 KB Output is correct
25 Correct 5554 ms 165320 KB Output is correct
26 Correct 6925 ms 155568 KB Output is correct
27 Correct 3763 ms 187724 KB Output is correct
28 Correct 2708 ms 153276 KB Output is correct
29 Correct 6569 ms 154408 KB Output is correct
30 Correct 6584 ms 153820 KB Output is correct
31 Correct 6651 ms 154384 KB Output is correct
32 Correct 1608 ms 74968 KB Output is correct
33 Correct 1671 ms 70276 KB Output is correct
34 Correct 2909 ms 65660 KB Output is correct
35 Correct 2767 ms 65576 KB Output is correct
36 Correct 3354 ms 66536 KB Output is correct
37 Correct 3415 ms 66432 KB Output is correct