結果

問題 No.1266 7 Colors
ユーザー polylogK
提出日時 2020-10-23 22:46:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 165 ms / 3,000 ms
コード長 2,963 bytes
コンパイル時間 2,306 ms
コンパイル使用メモリ 202,952 KB
最終ジャッジ日時 2025-01-15 13:40:08
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
002.cpp: In function ‘int main()’:
002.cpp:62:11: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘union_find::size_type’ {aka ‘long int’} [-Wformat=]
002.cpp:20:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
002.cpp:26:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
002.cpp:50:24: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]

ソースコード

diff #
プレゼンテーションモードにする

#line 1 "002.cpp"
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;
template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
#line 1 "/home/ecasdqina/cpcpp/libs/library_cpp/data_structure/union_find.hpp"
#line 6 "/home/ecasdqina/cpcpp/libs/library_cpp/data_structure/union_find.hpp"
class union_find {
public:
    using size_type = std::int_fast32_t;
    using container = std::vector<size_type>;
    
    container data;
    size_type comp_cnt;
private:
    const size_type find(size_type k) {
        if(data[k] < 0) return k;
        return data[k] = find(data[k]);
    }
public:
    union_find() = default;
    union_find(const union_find &) = default;
    union_find(union_find&&) = default;
    union_find & operator=(const union_find &) = default;
    union_find & operator=(union_find &&) = default;
    union_find(size_type N): data(N, -1), comp_cnt(N) {}
    bool unite(size_type x, size_type y) {
        x = find(x); y = find(y);
        if(x == y) return false;
        if(data[x] > data[y]) std::swap(x, y);
        
        data[x] += data[y];
        data[y] = x;
        comp_cnt--;
        return true;
    }
    
    bool is_united(size_type x, size_type y) { return find(x) == find(y); }
    size_type size() const { return data.size(); }
    size_type size(size_type k) { return -data[find(k)]; }
    size_type comp(size_type k) { return find(k); };
    size_type count() const { return comp_cnt; }
    size_type operator[](size_type k) { return find(k); }
    
    void swap(union_find & r) {
        data.swap(r.data);
        std::swap(comp_cnt, r.comp_cnt);
    }
};
#line 18 "002.cpp"
int main() {
    int n, m, q; scanf("%d%d%d", &n, &m, &q);
    std::vector<std::string> color(n);
    std::vector<int> x(m), y(m);
    std::vector<std::vector<int>> g(n);
    for(int i = 0; i < n; i++) std::cin >> color[i];
    for(int i = 0; i < m; i++) {
        scanf("%d%d", &x[i], &y[i]);
        x[i]--; y[i]--;
        g[x[i]].push_back(i);
        g[y[i]].push_back(i);
    }
    union_find uf(n * 7);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < 7; j++) {
            if(color[i][j] == '1' and color[i][(j + 1) % 7] == '1') {
                uf.unite(j * n + i, (j + 1) % 7 * n + i);
            }
        }
    }
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < 7; j++) {
            if(color[x[i]][j] == '1' and color[y[i]][j] == '1') {
                uf.unite(j * n + x[i], j * n + y[i]);
            }
        }
    }
    while(q--) {
        int type, a, b; scanf("%d%d%d", &type, &a, &b); a--; b--;
        if(type == 1) {
            color[a][b] = '1';
            if(color[a][(b + 6) % 7] == '1') uf.unite(b * n + a, (b + 6) % 7 * n + a);
            if(color[a][(b + 1) % 7] == '1') uf.unite(b * n + a, (b + 1) % 7 * n + a);
            for(auto id: g[a]) {
                int to = x[id] ^ y[id] ^ a;
                if(color[to][b] != '1') continue;
                uf.unite(b * n + a, b * n + to);
            }
        } else if(type == 2) {
            printf("%d\n", uf.size(a));
        }
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0