oj.uz

Submission #51343

# Submission time Handle Problem Language Result Execution time Memory
51343 2018-06-17T14:43:38 Z Kubalionzzale Sightseeing (NOI14_sightseeing) C++14
25 / 25
 3191 ms 102580 KB 
#include <iostream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <functional>

std::vector< std::vector< std::pair<int, int> > > g(500010);
int ans[500010] = { 0 }, sums[500010] = { 0 }, roots[500010] = { 0 };
std::pair<int, std::pair<int, int> > edge[5000010];
int n, m, q;

void initialize(int n)
{
    for (int i = 0; i < n; ++i)
    {
        roots[i] = i;
        sums[i] = 1;
    }
}

int root(int i)
{
    while (roots[i] != i)
    {
        roots[i] = roots[roots[i]];
        i = roots[i];
    }

    return i;
}

void makeUnion(int a, int b)
{
    a = root(a);
    b = root(b);

    if (sums[a] >= sums[b])
    {
        sums[a] += sums[b];
        roots[b] = roots[a];
    }
    else
    {
        sums[b] += sums[a];
        roots[a] = roots[b];
    }
}

void dfs(int index, int parent, int val)
{
    ans[index] = val;
    for (int i = 0; i < g[index].size(); ++i)
    {
        int next = g[index][i].second;
        int nextVal = g[index][i].first;
        if (next != parent)
        {
            dfs(next, index, std::min(nextVal, val));
        }
    }
}

int main()
{
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    scanf("%d%d%d", &n, &m, &q);
//    std::cin >> n >> m >> q;

    int x, y, quality;
    for (int i = 0; i < m; ++i)
    {
        scanf("%d%d%d", &x, &y, &quality);
//        std::cin >> x >> y >> quality;
        --x,
        --y;


        edge[i] = std::make_pair(quality, std::make_pair(x, y));
    }

    std::sort(edge, edge + m);

    int node[500010];
    for (int i = 0; i < q; ++i)
    {
        scanf("%d", &node[i]);
//        std::cin >> node[i];
    }

    bool in[500010] = { 0 };

    in[0] = true;
    initialize(n);
    for (int i = m - 1; i >= 0; --i)
    {
        x = edge[i].second.first;
        y = edge[i].second.second;
        int val = edge[i].first;

        if (root(x) != root(y))
        {
            makeUnion(root(x), root(y));
            g[x].push_back(std::make_pair(val, y));
            g[y].push_back(std::make_pair(val, x));
        }
    }

    dfs(0, -1, 1e6);

    for (int i = 0; i < q; ++i)
    {
        printf("%d\n", ans[node[i] - 1]);
//        std::cout << ans[node[i] - 1] << "\n";
    }
}

Compilation message

sightseeing.cpp: In function 'void dfs(int, int, int)':
sightseeing.cpp:54:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[index].size(); ++i)
                     ~~^~~~~~~~~~~~~~~~~
sightseeing.cpp: In function 'int main()':
sightseeing.cpp:93:10: warning: variable 'in' set but not used [-Wunused-but-set-variable]
     bool in[500010] = { 0 };
          ^~
sightseeing.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &x, &y, &quality);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &node[i]);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12152 KB Output is correct
2 Correct 11 ms 12152 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12332 KB Output is correct
2 Correct 12 ms 12332 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 14736 KB Output is correct
2 Correct 41 ms 14736 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2075 ms 67868 KB Output is correct
2 Correct 3191 ms 102580 KB Output is correct