Submission #983021

#	Time	Username	Problem	Language	Result	Execution time	Memory
983021		vjudge1	다리 (APIO19_bridges)	C++17	0 / 100	154 ms	5924 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

#define all(a) a.begin(), a.end()
#define print(a) for(auto x : a) cout << x << ' '; cout << endl;

struct DSU {

    vector<int> sz, parent;

    DSU (int n){
        sz.resize(n);
        parent.resize(n);
        for(int i = 0; i < n; i ++)
            parent[i] = i, sz[i] = 1;
    }

    void add(int a, int b){
        a = find_parent(a);
        b = find_parent(b);

        if(a == b)
            return;
        if(sz[a] < sz[b])
            swap(a, b);

        parent[b] = a;
        sz[a] += sz[b];
        sz[b] = 0;
    }

    int find_parent(int a){
        if(a != parent[a])
            return parent[a] = find_parent(parent[a]);
        return a;
    }

    int siz(int n){
        n = find_parent(n);
        return sz[n];
    }
};

signed main(){
    int n, m;
    cin >> n >> m;
    vector<array<int, 3>> ways(m);
    for(int i = 0; i < m; i ++)
        cin >> ways[i][2] >> ways[i][1] >> ways[i][0];
    int q;
    cin >> q;
    vector<array<int, 3>> query(q);
    for(int i = 0; i < q; i ++){
        int t, a, b;
        cin >> t >> a >> b;
        query[i] = {b, a, i};
    }
    sort(all(ways));
    sort(all(query));
    DSU d(n + 1);
    vector<int> ans(q);
    int left = 0, right = 0;
    while(left < ways.size() or right < query.size()){
        if(left == ways.size() or right < query.size() and query[right][0] <= ways[left][0]){
            ans[query[right][2]] = d.siz(query[right][1]);
            right ++;
        }
        else{
            d.add(ways[left][1], ways[left][2]);
            left ++;
        }
    }
    print(ans)
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     while(left < ways.size() or right < query.size()){
      |           ~~~~~^~~~~~~~~~~~~
bridges.cpp:63:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     while(left < ways.size() or right < query.size()){
      |                                 ~~~~~~^~~~~~~~~~~~~~
bridges.cpp:64:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         if(left == ways.size() or right < query.size() and query[right][0] <= ways[left][0]){
      |            ~~~~~^~~~~~~~~~~~~~
bridges.cpp:64:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         if(left == ways.size() or right < query.size() and query[right][0] <= ways[left][0]){
      |                                   ~~~~~~^~~~~~~~~~~~~~
bridges.cpp:64:56: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   64 |         if(left == ways.size() or right < query.size() and query[right][0] <= ways[left][0]){

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27