oj.uz

Submission #538216

# Submission time Handle Problem Language Result Execution time Memory
538216 2022-03-16T10:20:10 Z kabika Sightseeing (NOI14_sightseeing) C++14
25 / 25
 2222 ms 189888 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <queue>
using namespace std;
typedef long long ll;
constexpr int INF = 1e6 + 1;

struct UFDS
{
    vector<int> root, sz;
    UFDS(int n) :root(n), sz(n, 1)
    {
        iota(root.begin(), root.end(), 0);
    }
    int findRoot(int x)
    {
        if (x == root[x])
            return x;
        else
            return findRoot(root[x]);
    }
    bool same(int x, int y)
    {
        return (findRoot(x) == findRoot(y));
    }
    bool unite(int x, int y)
    {
        x = findRoot(x);
        y = findRoot(y);
        if (x == y)
            return 0;
        if (sz[x] < sz[y])
            swap(x, y);
        sz[x] += sz[y];
        root[y] = x;
        return 1;
    }
    int size(int x)
    {
        return sz[findRoot(x)];
    }
    void clean()
    {
        root.clear();
        sz.clear();
    }
};

struct Road
{
    int a, b, ql;
};

bool comp(Road r1, Road r2)
{
    return r1.ql > r2.ql;
}

vector<vector<Road>> mst;
vector<int> ans;
void bfs()
{
    queue<int> qu;
    qu.push(1);
    while (!qu.empty())
    {
        int p = qu.front();
        qu.pop();
        for (int i = 0; i < mst[p].size(); ++i)
        {
            if (ans[mst[p][i].b] == INF)
            {
                qu.push(mst[p][i].b);
                ans[mst[p][i].b] = min(mst[p][i].ql, ans[p]);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int v, e, q;
    cin >> v >> e >> q;
    vector<Road> rds(e);
    for (int i = 0; i < e; ++i)
        cin >> rds[i].a >> rds[i].b >> rds[i].ql;
    sort(rds.begin(), rds.end(), comp);

    mst.resize(v + 1);
    UFDS ds(v + 1);
    for (Road r : rds)
    {
        if (!ds.same(r.a, r.b))
        {
            ds.unite(r.a, r.b);
            mst[r.a].push_back(r);
            swap(r.a, r.b);
            mst[r.a].push_back(r);
        }
    }
    rds.clear();
    ds.clean();

    ans.resize(v + 1, INF);
    bfs();
    while (q--)
    {
        int x;
        cin >> x;
        cout << ans[x] << '\n';
    }
    return 0;
}

Compilation message

sightseeing.cpp: In function 'void bfs()':
sightseeing.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (int i = 0; i < mst[p].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4548 KB Output is correct
2 Correct 22 ms 4100 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1562 ms 123556 KB Output is correct
2 Correct 2222 ms 189888 KB Output is correct