oj.uz

Submission #973992

# Submission time Handle Problem Language Result Execution time Memory
973992 2024-05-02T14:29:22 Z canadavid1 Cities (BOI16_cities) C++14
14 / 100
 475 ms 33168 KB 
#include <iostream>
#include <vector>
#include <queue>

using Cost = long long;

struct uf
{
private:
    std::vector<int> data;
    int find(int val)
    {
        if (data[val] < 0) return val;
        return data[val] = find(data[val]);
    }
public:
    uf(int s) : data(s,-1) {}
    bool same(int a, int b)
    {
        return find(a)==find(b);
    }
    bool unite(int a, int b)
    {
        a = find(a);
        b = find(b);
        if (a==b) return false;
        if (-data[a] < -data[b]) std::swap(a,b);
        if (data[a] == data[b]) data[a]--;
        data[b] = a;
        return true;
    }
};

struct road
{
    int a,b;
    Cost cost;
};
struct city
{
    bool important=false;
    std::vector<std::pair<int,Cost>> neigh;
    Cost dist_to_important[5];
};

template<typename F>
void dijkstra(int start,std::vector<city>& cities, F callback)
{
    std::priority_queue<std::pair<Cost,int>> q;
    std::vector<bool> visit(cities.size(),0);
    q.emplace(0,start);
    while(q.size())
    {
        auto[cost,node] = q.top();q.pop();
        cost = -cost;
        if (visit[node]) continue;
        visit[node] = true;
        callback(cities[node],cost);
        for(auto[n,c] : cities[node].neigh) q.emplace(-cost-c,n);
    }
}

int main()
{
    std::cin.tie(0)->sync_with_stdio(false);
    int n,k,m;
    std::cin >> n >> k >> m;
    uf uf(n);
    std::vector<road> roads(m);
    std::vector<city> cities(n);
    std::vector<int> important(k);
    for(auto& i : important) 
    {
        std::cin >> i; i--;
        cities[i].important = true;
    }
    for(auto& r : roads) 
    {
        std::cin >> r.a >> r.b >> r.cost; r.a--; r.b--;
        cities[r.a].neigh.emplace_back(r.b,r.cost);
        cities[r.b].neigh.emplace_back(r.a,r.cost);
    }
    for(int i = 0; i < k; i++)
        dijkstra(important[i],cities,[i](city& c,Cost cost) {c.dist_to_important[i]=cost;});
    
    Cost c = 1ll<<62;
    if(k==2)
    {
        c = cities[important[1]].dist_to_important[0];
    }
    else if(k==3)
    {
        for(auto& n : cities) c = std::min(c,n.dist_to_important[0]+n.dist_to_important[1]+n.dist_to_important[2]);
    }
    else
    {
        
    }
    std::cout << c << "\n";
    

}

Compilation message

cities.cpp: In function 'void dijkstra(int, std::vector<city>&, F)':
cities.cpp:54:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |         auto[cost,node] = q.top();q.pop();
      |             ^
cities.cpp:59:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |         for(auto[n,c] : cities[node].neigh) q.emplace(-cost-c,n);
      |                 ^

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 33168 KB Output is correct
2 Correct 319 ms 32244 KB Output is correct
3 Correct 93 ms 16720 KB Output is correct
4 Correct 219 ms 31552 KB Output is correct
5 Correct 246 ms 32156 KB Output is correct
6 Correct 158 ms 31592 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 648 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 405 ms 32812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 475 ms 32300 KB Output isn't correct
2 Halted 0 ms 0 KB -