EDITORWARS 문제 입력 관련하여 질문드립니다.

  • sven
    sven

    EDITORWARS

    #include <vector>
    #include <algorithm>
    #include <iostream>
    #include <string>
    #include <cassert>
    
    using namespace std;
    
    typedef vector<int> VI;
    
    #define PB push_back
    #define REP(i,n) for(int i=0; i<(n); ++i)
    
    #define ASF assert(false);
    
    struct BipartiteDisjointSet {
      VI parent, rank, enemy, size;
      //parent : [1,n)
      BipartiteDisjointSet(int n) : parent(n), rank(n, 1) , enemy(n, -1), size(n, 1) {
        REP(i, n) parent[i] = i;
      }
      int find(int u) {
        if(u == parent[u]) return u;
        return parent[u] = find(parent[u]);
      }
      int merge(int u, int v) {
        if(u == -1 or v == -1) return max(u, v);
        u = find(u); v = find(v);
        if(u == v) return u;
        if(rank[u] > rank[v]) swap(u, v);
        if(rank[u] == rank[v]) ++rank[v];
        parent[u] = v;
        size[v] += size[u];
        return v;
      }
      bool dis(int u, int v) {
        u = find(u); v = find(v);
        if(u == v) return false;
        int a = merge(u, enemy[v]), b = merge(v, enemy[u]);
        enemy[a] = b; enemy[b] = a;
        return true;
      }
      bool ack(int u, int v) {
        u = find(u); v = find(v);
        if(enemy[u] == v) return false;
        int a = merge(u, v), b = merge(enemy[u], enemy[v]);
        enemy[a] = b;
        if(b != -1) enemy[b] = a;
        return true;
      }
      int maxParty() {
        int ret = 0;
        REP(i, parent.size())
          if(this->find(i) == i) {
            int enemy = this->enemy[i];
            if(enemy > i) continue;
            int mySize = this->size[i];
            int enemySize = (enemy == -1 ? 0 : this->size[enemy]);
            ret += max(mySize, enemySize);
          }
        return ret;
      }
    };
    
    int N, M;
    int solve() {
      cin >> N >> M;
      BipartiteDisjointSet A(N);
      REP(i, M) {
        int u, v;
        string str;
        cin >> str >> u >> v;
        assert(str.size());
        if(str == "ACK") {
          if(not A.ack(u, v)) return -(i+1);
        }
        else if(str == "DIS") {
          if(not A.dis(u, v)) return -(i+1);
        }
        /*else ASF*/
      }
      return A.maxParty();
    }
    
    int main() {
      int T; cin >> T; REP(i, T) {
        int ret = solve();
        if(ret < 0) cout << "CONTRADICTION AT " << -ret << endl;
        else cout << "MAX PARTY SIZE IS " << ret << endl;
      }
      return 0;
    }
    

    책과 같게 짜려고 했는데요, 입력을 받는 부분에서 문제가 있는 것 같습니다. 제출하면 RTE (SIGABRT: program aborted, probably assertion fail) 가 뜨는데요, assert 는 assert(str.size()) 에서만 사용되었습니다. character 배열로도 시도해보았지만 마찬가지 결과가 뜹니다. 어디서 실수한 것인지 잘 모르겠습니다ㅜㅜ 조언 부탁드립니다.


    10년 전
2개의 댓글이 있습니다.
  • JongMan
    JongMan

    다음 입력을 한 번 돌려보세요. :)

    3
    3 4
    ACK 0 1
    ACK 1 2
    DIS 2 0
    ACK 0 1
    3 3
    ACK 0 1
    ACK 1 2
    DIS 2 0


    10년 전 link
  • sven
    sven

    아... 감사합니다!


    10년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.