Submission #516636

#	Time	Username	Problem	Language	Result	Execution time	Memory
516636		Be_dos	Evacuation plan (IZhO18_plan)	C++17	100 / 100	709 ms	58084 KiB

plan

#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
#include <cassert>

int32_t* answers;

struct DSU {
    int32_t* parents;
    std::set<int32_t>* per_comp;

    DSU(int32_t n) {
        parents = new int32_t[n];
        per_comp = new std::set<int32_t>[n];
        for(int32_t i = 0; i < n; i++)
            parents[i] = i;
    }

    int32_t get_root(int32_t v) {
        if(parents[v] == v)
            return v;
        return parents[v] = get_root(parents[v]);
    }

    void join(int32_t v1, int32_t v2, int32_t answer_if) {
        v1 = get_root(v1);
        v2 = get_root(v2);
        if(v1 == v2)
            return;
        if(per_comp[v1].size() < per_comp[v2].size())
            std::swap(v1, v2);
        for(auto it = per_comp[v2].begin(); it != per_comp[v2].end(); it++)
            if(per_comp[v1].find(*it) != per_comp[v1].end()) {
                answers[*it] = answer_if;
            } else
                per_comp[v1].insert(*it);
        parents[v2] = v1;
    }
};

void dijkstra(std::vector<int32_t>& starts, int32_t n, std::vector<std::pair<int32_t, int32_t> >* graph, int32_t* dist) {
    for(int32_t i = 0; i < n; i++)
        dist[i] = INT32_MAX;
    std::set<std::pair<int32_t, int32_t> > active;
    for(int32_t i = 0; i < starts.size(); i++) {
        dist[starts[i]] = 0;
        active.emplace(0, starts[i]);
    }
    while(!active.empty()) {
        int32_t v = active.begin()->second;
        active.erase(active.begin());

        for(int32_t i = 0; i < graph[v].size(); i++)
            if(dist[v] + graph[v][i].second < dist[graph[v][i].first]) {
                auto it = active.find({dist[graph[v][i].first], graph[v][i].first});
                if(it != active.end())
                    active.erase(it);
                dist[graph[v][i].first] = dist[v] + graph[v][i].second;
                active.emplace(dist[graph[v][i].first], graph[v][i].first);
            }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int32_t n, m;
    std::cin >> n >> m;

    std::vector<std::pair<int32_t, int32_t> >* graph = new std::vector<std::pair<int32_t, int32_t> >[n];
    for(int32_t i = 0; i < m; i++) {
        int32_t src, dst, weight;
        std::cin >> src >> dst >> weight;
        src--;
        dst--;

        graph[src].emplace_back(dst, weight);
        graph[dst].emplace_back(src, weight);
    }

    int32_t k;
    std::cin >> k;

    std::vector<int32_t> starts;
    for(int32_t i = 0; i < k; i++) {
        int32_t v;
        std::cin >> v;
        v--;

        starts.push_back(v);
    }

    int32_t* dist = new int32_t[n];
    dijkstra(starts, n, graph, dist);

    int32_t num_q;
    std::cin >> num_q;

    DSU dsu(n);
    for(int32_t q = 0; q < num_q; q++) {
        int32_t src, dst;
        std::cin >> src >> dst;
        src--;
        dst--;

        dsu.per_comp[src].insert(q);
        dsu.per_comp[dst].insert(q);
    }

    answers = new int32_t[num_q];
    int32_t* order = new int32_t[n];
    for(int32_t i = 0; i < n; i++)
        order[i] = i;
    std::sort(order, order + n, [&](int32_t v1, int32_t v2) {
        return dist[v1] > dist[v2];
    });
    bool* active = new bool[n];
    for(int32_t i = 0; i < n; i++)
        active[i] = false;
    for(int32_t i = 0; i < n; i++) {
        active[order[i]] = true;
        for(int32_t j = 0; j < graph[order[i]].size(); j++)
            if(active[graph[order[i]][j].first])
                dsu.join(order[i], graph[order[i]][j].first, dist[order[i]]);
    }

    for(int32_t q = 0; q < num_q; q++)
        std::cout << answers[q] << "\n";
    return 0;
}
         

Compilation message (stderr)

plan.cpp: In function 'void dijkstra(std::vector<int>&, int32_t, std::vector<std::pair<int, int> >*, int32_t*)':
plan.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int32_t i = 0; i < starts.size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~
plan.cpp:71:30: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(int32_t i = 0; i < graph[v].size(); i++)
      |                            ~~^~~~~~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:141:30: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |         for(int32_t j = 0; j < graph[order[i]].size(); j++)
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46