Submission #752314

#	Time	Username	Problem	Language	Result	Execution time	Memory
752314		anaduguleanu	Factories (JOI14_factories)	C++14	100 / 100	6925 ms	187724 KiB

factories

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

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67