제출 #1366902

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1366902		atharva_a_b	다리 (APIO19_bridges)	C++17	13 / 100	3094 ms	16184 KiB

bridges

#include <iostream>
#include <vector>
#include <set>
#include <queue>

struct edge {
    int32_t v, d, i;

    bool operator<(const edge& other_e) const {
        return i < other_e.i;
    }
};

typedef std::vector<std::set<edge>> adjacency_list;

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

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

    if(n == 1) {
        int32_t q;
        std::cin >> q;
        while(q--) std::cout << "1\n";
        return 0;
    }

    int32_t i, u, v, d;

    adjacency_list adj_list(n);
    std::vector<std::pair<int32_t, int32_t>> endpoints(m);
    for(i = 0; i < m; ++i) {
        std::cin >> u >> v >> d;
        --u, --v;

        adj_list[u].insert({v, d, i});
        adj_list[v].insert({u, d, i});
        endpoints[i] = {u, v};
    }

    int32_t q;
    std::cin >> q;

    int32_t t, w;

    std::vector<bool> visited(n, false);
    std::queue<int32_t> qu;

    int32_t ans;

    while(q--) {
        std::cin >> t;

        if(t == 1) {
            std::cin >> i >> d;
            --i;
            u = endpoints[i].first, v = endpoints[i].second;

            adj_list[u].erase({-1, -1, i});
            adj_list[u].insert({v, d, i});
            adj_list[v].erase({-1, -1, i});
            adj_list[v].insert({u, d, i});
        } else {
            std::cin >> u >> w;
            --u;

            qu.push(u);
            ans = 1;
            visited[u] = true;

            do {
                u = qu.front();
                qu.pop();

                for(auto& e: adj_list[u]) {
                    if(!visited[e.v] && w <= e.d) {
                        ++ans;
                        visited[e.v] = true;
                        qu.push(e.v);
                    }
                }
            } while(!qu.empty());

            std::cout << ans << "\n";

            for(u = 0; u < n; ++u) visited[u] = false;
        }
    }

    return 0;
}

• 서브태스크 1: 13 / 13
• 서브태스크 2: 0 / 16
• 서브태스크 3: 0 / 17
• 서브태스크 4: 0 / 14
• 서브태스크 5: 0 / 13
• 서브태스크 6: 0 / 27