結果

問題 No.2618 除霊
ユーザー startcpp
提出日時 2022-02-06 17:15:14
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 515 ms / 2,000 ms
コード長 9,647 bytes
コンパイル時間 1,398 ms
コンパイル使用メモリ 109,764 KB
実行使用メモリ 43,176 KB
最終ジャッジ日時 2024-06-28 22:29:53
合計ジャッジ時間 23,819 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 43
権限があれば一括ダウンロードができます
コンパイルメッセージ
In member function 'void FastSolver::add_near(int)',
    inlined from 'virtual std::vector<int> FastSolver::solve(Testcase&)' at main.cpp:407:14:
main.cpp:338:21: warning: 'x' may be used uninitialized [-Wmaybe-uninitialized]
  338 |                 int bfs_v = to_bfs[v];
      |                     ^~~~~
main.cpp: In member function 'virtual std::vector<int> FastSolver::solve(Testcase&)':
main.cpp:398:37: note: 'x' was declared here
  398 |                                 int x;
      |                                     ^

ソースコード

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

//3解法間のストレステスト
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <random>
using namespace std;
mt19937 mt(252521); //乱数生成器, メルセンヌ・ツイスタ
//Union Find Tree
struct UF {
    int n;
    vector<int> par;
    int merge_cnt;
    void init(int n) {
        this->n = n;
        par.resize(n);
        for (int i = 0; i < n; i++) {
            par[i] = i;
        }
        merge_cnt = 0;
    }
    int root(int x) {
        if (par[x] == x) { return x; }
        return par[x] = root(par[x]);
    }
    bool same(int x, int y) { return root(x) == root(y); }
    void merge(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            par[x] = y;
            merge_cnt++;
        }
    }
};
//テストケース構造体
class Testcase {
private:
    vector<int> a, b;
public:
    int n;
    vector<vector<int>> edge_to;
    string color;
    void generate(int n) {
        UF uf;
        uf.init(n);
        edge_to.resize(n);
        this->n = n;
        while (uf.merge_cnt < n - 1) {
            int u = mt() % n;
            int v = mt() % n;
            if (uf.same(u, v) == false) {
                uf.merge(u, v);
                a.push_back(u);
                b.push_back(v);
                edge_to[u].push_back(v);
                edge_to[v].push_back(u);
            }
        }
        for (int i = 0; i < n; i++) {
            if (mt() % 100 < 50) {
                color += 'b';
            }
            else {
                color += 'w';
            }
        }
    }
    
    void input() {
        cin >> n;
        edge_to.resize(n);
        for (int i = 0; i < n - 1; i++) {
            int a, b;
            cin >> a >> b;
            a--; b--;
            edge_to[a].push_back(b);
            edge_to[b].push_back(a);
        }
        int m; cin >> m;
        color = "";
        for (int i = 0; i < n; i++) color += 'w';
        for (int i = 0; i < m; i++) {
            int v; cin >> v; v--;
            color[v] = 'b';
        }
    }
    void print() {
        cout << n << endl;
        for (int i = 0; i < n - 1; i++) {
            cout << a[i] << " " << b[i] << endl;
        }
        cout << color << endl;
    }
};
//Solverの基底クラス
class Solver {
protected:
    int n;
    vector<int> edge_to[200000];
    string color;
    void input(Testcase &testcase) {
        n = testcase.n;
        for (int i = 0; i < n; i++) {   
            edge_to[i] = testcase.edge_to[i];
        }
        color = testcase.color;
    }
    virtual vector<int> solve(Testcase &testcase) = 0;
};
//ナイーブ解1：O(N^2)
class NaiveSolver1 : public Solver {
private:
    vector<int> operate(int v) {
        vector<int> blacks;
        if (color[v] == 'b') {
            blacks.push_back(v);
        }
        for (int nv : edge_to[v]) { //vの隣接頂点nv
            if (color[nv] == 'b') {
                blacks.push_back(nv);
            }
        }
        for (int b : blacks) {
            color[b] = 'w';
        }
        return blacks;
    }
    bool is_danger(int v) {
        if (color[v] == 'b') { return true; }
        for (int nv : edge_to[v]) {
            if (color[nv] == 'b') { return true; }
        }
        return false;
    }
    int calc() {
        int ret = 0;
        
        for (int v = 0; v < n; v++) { //頂点vについて危険かを調べる
            if (is_danger(v)) {
                ret++;
            }
        }
        return ret;
    }
    void revert(vector<int> change_vs) {
        for (int v : change_vs) {
            color[v] = 'b';
        }
    }
public:
    vector<int> solve(Testcase &testcase) {
        input(testcase);
        
        vector<int> ans;
        for (int v = 0; v < n; v++) {
            vector<int> change_vs = operate(v); //色を変更した頂点リストを返す
            ans.push_back(calc());
            revert(change_vs);
        }
        
        return ans;
    }
};
//ナイーブ解2: O(N^2), ランダムグラフのとき高速
class NaiveSolver2 : public Solver {
private:
    int cnt_black[200000];  //cnt_black[v] = 頂点v自身・vの隣接頂点のうち黒であるものの個数
    int safe_cnt;           //safe_cnt = cnt_black[v]が0であるような頂点vの個数
    void calc_init() {
        safe_cnt = 0;
        for (int v = 0; v < n; v++) {
            cnt_black[v] = 0;
            
            if (color[v] == 'b') {
                cnt_black[v]++;
            }
            for (int nv : edge_to[v]) {
                if (color[nv] == 'b') {
                    cnt_black[v]++;
                }
            }
            
            if (cnt_black[v] == 0) {
                safe_cnt++;
            }
        }
    }
    vector<int> operate(int v) {
        vector<int> blacks;
        if (color[v] == 'b') {
            blacks.push_back(v);
        }
        for (int nv : edge_to[v]) {
            if (color[nv] == 'b') {
                blacks.push_back(nv);
            }
        }
        for (int u : blacks) { //頂点uについて、uから距離1以内の頂点xのcnt_black[x]を1減らす
            cnt_black[u]--;
            if (cnt_black[u] == 0) { safe_cnt++; }
            for (int x: edge_to[u]) {
                cnt_black[x]--;
                if (cnt_black[x] == 0) { safe_cnt++; }
            }
        }
        return blacks;
    }
    void revert(vector<int> change_vs) {
        for (int v : change_vs) {
            if (cnt_black[v] == 0) { safe_cnt--; }
            cnt_black[v]++;
            for (int x : edge_to[v]) {
                if (cnt_black[x] == 0) { safe_cnt--; }
                cnt_black[x]++;
            }
        }
    }
public:
    vector<int> solve(Testcase &testcase) {
        input(testcase);
        calc_init();
        vector<int> ans;
        for (int v = 0; v < n; v++) {
            vector<int> change_vs = operate(v);
            ans.push_back(n - safe_cnt);
            revert(change_vs);
        }
        return ans;
    }
};
//想定解: O(N), デバッグ済み
class FastSolver : public Solver {
private:
    int black[200000];      //black[v] = vと隣接する黒頂点の個数
    int to_bfs[200000];
    int parent_bfs[200000];
    int child_bfs_l[200000], child_bfs_r[200000];   //[l, r]
    int safe_bfs[200001];   //safe_bfs[bfsId] = BFS順序でbfsId番の頂点について操作をおこなった場合の、危険でない頂点の個数
    void init_member() {
        for (int i = 0; i < n; i++) {
            black[i] = 0;
            to_bfs[i] = 0;
            parent_bfs[i] = 0;
            child_bfs_l[i] = 0;
            child_bfs_r[i] = 0;
            safe_bfs[i] = 0;
        }
        safe_bfs[n] = 0;
    }
    void bfs(int root_v) {
        vector<bool> used(n, false);
        queue<int> que;
        int t = 0;
        for (int bfs_v = 0; bfs_v < n; bfs_v++) {
            parent_bfs[bfs_v] = -1;
            child_bfs_l[bfs_v] = -1;
            child_bfs_r[bfs_v] = -1;
        }
        to_bfs[root_v] = t;
        t++;
        que.push(root_v);
        used[root_v] = true;
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            for (int nv : edge_to[v]) {
                if (used[nv]) { continue; }
                to_bfs[nv] = t;
                parent_bfs[t] = to_bfs[v];
                if (child_bfs_l[to_bfs[v]] == -1) { child_bfs_l[to_bfs[v]] = t; }   //最初見る子のbfsIdになる
                child_bfs_r[to_bfs[v]] = t; //最後見る子のbfsIdになる
                t++;
                que.push(nv);
                used[nv] = true;
            }
        }
    }
    //safe_bfs[l, r) += 1, を階差数列上でおこなう
    void add(int l, int r) {
        if (debug_flag) {
            printf("safe_bfs[%d, %d] += 1\n", l, r);
        }
        safe_bfs[l]++;
        safe_bfs[r + 1]--;
    }
    void add_near(int v) {
        int bfs_v = to_bfs[v];
        int l = child_bfs_l[bfs_v];
        int r = child_bfs_r[bfs_v];
        int p = parent_bfs[bfs_v];
        //v自身
        add(bfs_v, bfs_v);
        //vの子[l, r] (vが葉でないとき)
        if (l != -1) {
            add(l, r);
        }
        //vの親（vが根でないとき）
        if (p != -1) {
            add(p, p);
        }
    }
public:
    bool debug_flag;
    FastSolver() { debug_flag = false; }
    vector<int> solve(Testcase &testcase) {
        input(testcase);
        init_member();
        for (int v = 0; v < n; v++) {
            for (int nv : edge_to[v]) {
                if (color[nv] == 'b') {
                    black[v]++;
                }
            }
        }
        bfs(0);
        if (debug_flag) {
            cout << " id | to_bfs, parent_bfs, child_bfs_l, child_bfs_r" << endl;
            cout << "--------------------------------------------------" << endl;
            for (int v = 0; v < n; v++) {
                printf("%3d | %6d, %10d, %11d, %11d\n", v, to_bfs[v], parent_bfs[to_bfs[v]], child_bfs_l[to_bfs[v]], child_bfs_r[to_bfs[v]]);
            }
        }
        for (int v = 0; v < n; v++) { //頂点vが安全になる操作uをカウントアップ
            if (debug_flag) {
                printf("\n");
                printf("black[%d] = %d, color[%d] = %c\n", v, black[v], v, color[v]);           
            }
            if (black[v] == 0) {
                if (color[v] == 'w') { //u: 全頂点, imos法で区間[0, n)に加算
                    add(0, n - 1);
                }
                else {
                    add_near(v);    //v自身とvの隣接頂点に加算
                }
            }
            else if (black[v] == 1) {
                int x;
                for (int nv : edge_to[v]) { //v=0,..,Nにおけるループ回数の和は次数の和 = 2N - 2.
                    if (color[nv] == 'b') {
                        x = nv;
                        break;
                    }
                }
                
                if (color[v] == 'w') {  
                    add_near(x);    //x自身とxの隣接頂点に加算、ここの高速化がデカい！
                }
                else {
                    int bfs_x = to_bfs[x];
                    int bfs_v = to_bfs[v];
                    add(bfs_x, bfs_x);
                    add(bfs_v, bfs_v);
                }
            }
            else {  //操作uで頂点vを安全にするには、u = vとするしかない！
                int bfs_v = to_bfs[v];
                add(bfs_v, bfs_v);
            }
        }
        //累積和を取る
        for (int i = 0; i < n; i++) {
            safe_bfs[i + 1] += safe_bfs[i];
        }
        //答えを出力する
        if (debug_flag) {
            puts("");
        }
        vector<int> ans;
        for (int v = 0; v < n; v++) {
            if (debug_flag) {
                printf("safe_bfs[%d] = %d\n", v, safe_bfs[v]);
            }
            int bfs_v = to_bfs[v];
            ans.push_back(n - safe_bfs[bfs_v]);
        }
        return ans;
    }
};
NaiveSolver1 solver1;
NaiveSolver2 solver2;
FastSolver solver3;
bool stress_test(int caseNum, int N, Testcase &return_case) {
    for (int T = 0; T < caseNum; T++) {
        int n = N;
        Testcase testcase;
        testcase.generate(n);
        vector<int> ans1 = solver1.solve(testcase);
        vector<int> ans3 = solver3.solve(testcase);
        if (ans1 != ans3) {
            cout << "Wrong Answer[" << T << "]" << endl;
            cout << "Testcase (0-idx):" << endl;
            testcase.print();
            cout << endl;
            cout << "Different Answer (0-idx):" << endl;
            for (int i = 0; i < n; i++) {
                if (ans1[i] != ans3[i]) {
                    cout << i << " : " << ans1[i] << ", " << ans3[i] << endl;
                }
            }
            return_case = testcase;
            return true;
        }
    }
    cout << "Accepted" << endl;
    return false;
}
int main() {
    /*Testcase testcase;
    bool is_wrong = stress_test(1000, 15, testcase);
    if (is_wrong) {
        solver3.debug_flag = true;
        solver3.solve(testcase);
    }*/
    
    Testcase testcase;
    testcase.input();
    vector<int> ans = solver3.solve(testcase);
    for (int i = 0; i < ans.size(); i++) cout << ans[i] << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0